407673: GYM102870 C Closestools of Orz Pandas

There is a restroom for male Orz Pandas with $$$n$$$ closestools, labeled $$$1, 2, \cdots, n$$$. The distance between the closestool $$$i$$$ and the closestool $$$j$$$ is $$$|i - j|$$$.

The Orz Pandas are somewhat self-closed. When an Orz Panda enters the restroom, he will choose a closestool $$$x$$$, to make the distance between $$$x$$$ and any other closestools already occupied by another Orz Panda as large as possible.

If there are mulitple closestools satisifying this condition, the Orz Panda will choose the one with the smallest label.

Please write a program to simulate the operation of this restroom.

There are multiple test cases. Please process until EOF.

For each test case, the first line contains two integers $$$n$$$ and $$$m$$$, where $$$n$$$ is the number of closestools, and $$$m$$$ is the number of operations. Each of the next $$$m$$$ lines contains an operation. An operation may be one of the following:

• 1: an Orz Panda enters the restroom
• 2 x: the Orz Panda entered the restroom at the $$$x$$$-th operation leaves the restroom

It's guaranteed that $$$1 \leq n \leq 10^9$$$, $$$1 \leq m \leq 10^5$$$, and the sum of $$$m$$$ in all test cases will not exceed $$$10^6$$$. For each type 2 operation, it's guaranteed that $$$x$$$ is unique and the $$$x$$$-th operation is always a previous type 1 operation. It's guaranteed that the number of Orz Pandas in the restroom will not exceed $$$n$$$ at any time.

For each type 1 operation, output one line, containing the label of the closestool the entering Orz Panda will choose.

7 10
1
1
1
1
1
2 3
1
2 4
2 5
1

1
7
4
2
3
5
3