C. Closestools of Orz Pandas
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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.

Output

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

Example
Input
7 10
1
1
1
1
1
2 3
1
2 4
2 5
1
Output
1
7
4
2
3
5
3