영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
(그림은 원문 저장소에서 볼 수 있습니다)
cc by-sa
Winston works at the cinema “Absolute Cinema”, the peak cinema in the entire country. The auditorium has N numbered seats, and Winston's job is to keep exact track of which seats are available and which are already taken.
At the start of the day all seats are available. During the day, Q events occur. Visitors line up and shout various requests to Winston.
Winston does not have much time, so he must answer quickly and correctly.
When a visitor says: “I want to sit at seat i”, Winston checks the system:
- If seat i is available, Winston replies “Ledig” (Swedish word for Available) and marks it as taken.
- Otherwise Winston replies “Upptagen” (Swedish word for Occupied).
When a visitor says: “I want to move from seat i to seat j”, Winston first checks seat j:
- If seat j is occupied, Winston replies “Upptagen” and nothing changes.
- If seat j is available, Winston moves the person: seat i becomes available and seat j becomes taken, and he replies “Ledig”.
After each request Winston must always report whether the relevant seat is available or not. This is how Absolute Cinema keeps its peak order, and it is thanks to Winston that the cinema runs so well.
Input
The input consists of two integers N (1 ≤ N ≤ 10^9) and Q (1 ≤ Q ≤ 2 · 10^5), the number of seats in the auditorium and the number of events. All N seats are initially available.
Then follow Q lines describing events. Each line has one of the following formats:
1 i, a visitor wants to sit at seat i (1 ≤ i ≤ N).2 i j, a visitor at seat i wants to move to seat j (1 ≤ i, j ≤ N, i ≠ j). For each such query it is guaranteed that seat i is occupied.
Output
For each event, print exactly one line:
- Print
Ledigif the target seat was available (and perform the change). - Otherwise print
Upptagen.
Scoring
Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 15 | Q ≤ 10^3, N ≤ 10^4 |
| 2 | 25 | N ≤ 10^4 |
| 3 | 20 | No move requests will occur. |
| 4 | 40 | No additional constraints. |
Explanation of Sample 1
In the first example, there are 5 seats and 3 events:
- A visitor wants to sit in seat 1. Seat 1 is free, so Winston replies “Ledig”.
- A visitor wants to sit in seat 3. Seat 3 is free, so Winston replies “Ledig”.
- A visitor wants to sit in seat 3. Seat 3 is occupied, so Winston replies “Upptagen”.
Explanation of Sample 2
In the second example, there are 5 seats and 3 events:
- A visitor wants to sit in seat 1. Seat 1 is free, so Winston replies “Ledig”.
- A visitor in seat 1 wants to move to seat 2. Seat 2 is free, so Winston moves the person and replies “Ledig”.
- A visitor wants to sit in seat 1. Seat 1 is free (since the previous visitor moved), so Winston replies “Ledig”.
예제
예제 1
5 3 1 1 1 3 1 3
Ledig Ledig Upptagen
예제 2
5 3 1 1 2 1 2 1 1
Ledig Ledig Ledig
예제 3
10 6 1 2 1 3 1 6 2 6 7 1 10 1 7
Ledig Ledig Ledig Ledig Ledig Upptagen
예제 4
100 10 1 14 1 51 1 93 1 9 1 52 2 9 93 1 14 2 14 93 1 22 2 51 14
Ledig Ledig Ledig Ledig Ledig Upptagen Upptagen Upptagen Ledig Upptagen