Ants in a Corridor

A corridor is a segment of length $L$. The corridor carries coordinates: its left endpoint is $0$, its right endpoint is $L$, and the point that divides the corridor internally in the ratio $x : y$ has coordinate $\frac{xL}{x+y}$.

Whenever Gyeonggeun is bored, he puts one more ant on the corridor. Every ant on this corridor moves either left or right and covers distance $1$ per second. The corridor is only wide enough for one ant. When two ants moving in opposite directions meet at a point, both reverse direction at once and keep the same speed. An ant that reaches an endpoint of the corridor also reverses direction at once and keeps the same speed. Treat an ant as a point with no size. Two ants collide only when their coordinates are exactly equal, and an ant turns around only when its coordinate is exactly $0$ or exactly $L$.

At time $0$ seconds the corridor holds no ants. Write a program that processes $Q$ operations of the following two kinds.

1. At second $t$, put an ant moving right or left at coordinate $x$. If this ant is the $i$-th one placed, it gets number $i$.
2. Print the coordinate of ant number $i$ at second $t$.

The first line contains two positive integers $L$ and $Q$ ($1 \le L \le 10^9$, $1 \le Q \le 2 \times 10^5$).

Each of the next $Q$ lines holds one operation. Every line starts with an integer $t$ ($0 \le t \le 10^{18}$), the second at which the operation happens, and a positive integer $p$ ($1 \le p \le 2$), the kind of the operation. The rest of the line is as follows.

• If $p = 1$, an integer $x$ ($0 < x < L$) and an integer $d$ ($d \in \{-1, 1\}$) follow. At second $t$ an ant is placed at coordinate $x$, moving right when $d = 1$ and left when $d = -1$. The input never places an ant on a coordinate that another ant occupies at that second.
• If $p = 2$, the number $i$ of the ant follows. It is at least $1$ and at most the number of ants placed so far. Print the coordinate of ant number $i$ at second $t$.

The operations come in increasing order of $t$, and no two operations share the same $t$.

For each operation with $p = 2$, print the coordinate of that ant on its own line. Under these constraints the coordinate at a query time is always an integer, so print it as an integer.