Shuttle bus

Time limit1.5sMemory limit512 MB

Summary

Process students getting off a shuttle; after each exit every student shifts toward the nearer end one adjacent empty seat at a time, and queries ask who sits in a given seat.

Level: Medium7 of 10
Topics: Union-find, Simulation, Implementation
Solved: No attempts yet

Problem

A campus shuttle bus has $N$ seats in one row along a wall. The leftmost seat is seat 1 and the rightmost seat is seat $N$ . The bus picks up $N$ students at the main gate and departs, and each student takes one seat. The student who sits in seat $i$ at departure is called student $i$ .

Students like to doze off leaning on a partition, so they want to sit as close to either end as possible. When the student right next to them gets off or moves away and that seat becomes empty, a student moves into it if the move shortens the distance to the nearer of seat 1 and seat $N$ . The distance of seat $j$ is $\min(j-1,\ N-j)$ . As soon as one student gets off, every student follows this rule until nobody can move any more.

Chansu, the driver, wants to know who is sitting where. Write a program that processes the following two operations in the order they are given.

1 x : student $x$ gets off the bus. This student is guaranteed to be on board.
2 x : print the number of the student sitting in seat $x$ . If the seat is empty, print 0.

The bus is on its way to the garage, so no new student ever gets on.

Input

The first line contains the number of seats $N$ and the number of operations $M$ , separated by a space. ( $1 \le N \le 200\,000$ , $1 \le M \le 400\,000$ )

Each of the next $M$ lines contains the type of an operation (1 or 2) and $x$ , separated by a space. ( $1 \le x \le N$ ) At least one operation of type 2 is given.

Output

Print the result of each type 2 operation on its own line, in the order the operations are given.

Note

The pictures below show how the seats change on a bus with 6 seats as students get off one by one.

When student 1 gets off, student 2 and then student 3 move left. Student 4 stays put, because moving into seat 3 leaves the distance to the nearer end unchanged.

When student 3 gets off, seat 2 would be better for student 4, but it is not the seat right next to them, so student 4 does not move.

When student 5 gets off, student 4 moves right.

Examples7

Example 1

Input

Expected output

Example 2
Input
```
1 3
2 1
1 1
2 1
```
Expected output
```
1
0
```
Example 3
Input
```
2 5
2 1
2 2
1 1
2 1
2 2
```
Expected output
```
1
2
0
2
```
Example 4
Input
```
3 4
1 3
2 1
2 2
2 3
```
Expected output
```
1
0
2
```
Example 5
Input
```
5 6
1 4
2 1
2 2
2 3
2 4
2 5
```
Expected output
```
1
2
0
3
5
```
Example 6
Input
```
5 6
1 1
2 1
2 2
2 3
2 4
2 5
```
Expected output
```
2
3
0
4
5
```

Example 7

Input

Expected output