통로 위의 개미

길이가 $L$인 선분 모양의 통로가 있다. 통로에는 좌표가 붙어 있다. 왼쪽 끝점의 좌표는 $0$, 오른쪽 끝점의 좌표는 $L$이고, 통로를 $x : y$로 내분하는 점의 좌표는 $\frac{xL}{x+y}$다.

경근이는 심심할 때마다 통로 위에 개미를 한 마리씩 올린다. 이 통로에 올라간 개미는 반드시 왼쪽이나 오른쪽으로 1초에 거리 1씩 움직인다. 통로의 폭은 개미 한 마리만 지나갈 만큼 좁다. 서로 반대 방향으로 움직이던 두 개미가 한 점에서 만나면 그 즉시 둘 다 방향을 반대로 바꾸고 속력은 그대로 유지한다. 개미가 통로의 끝점에 닿을 때도 그 즉시 방향을 반대로 바꾸고 속력을 유지한다. 개미는 크기가 없는 점으로 다룬다. 두 개미는 좌표가 정확히 같아야 부딪히고, 좌표가 정확히 $0$이나 $L$이어야 방향을 바꾼다.

시각 $0$초에는 통로 위에 개미가 한 마리도 없다. 다음 두 종류의 동작 $Q$개를 처리하는 프로그램을 작성하라.

1. $t$초에 좌표가 $x$인 지점에 오른쪽이나 왼쪽으로 움직이는 개미를 올린다. 이 개미가 $i$번째로 올라간 개미라면 번호 $i$를 받는다.
2. $t$초일 때 $i$번 개미의 좌표를 출력한다.

첫 줄에 자연수 $L$과 $Q$가 주어진다 ($1 \le L \le 10^9$, $1 \le Q \le 2 \times 10^5$).

다음 $Q$개의 줄에 처리할 동작이 한 줄에 하나씩 주어진다. 각 줄은 동작이 일어나는 시각을 나타내는 정수 $t$ ($0 \le t \le 10^{18}$)와 동작의 종류를 나타내는 자연수 $p$ ($1 \le p \le 2$)로 시작하고, 그 뒤는 다음과 같다.

• $p = 1$이면 개미를 올릴 좌표 $x$ ($0 < x < L$)와 방향을 나타내는 정수 $d$ ($d \in \{-1, 1\}$)가 이어진다. $t$초에 좌표 $x$인 지점에 개미를 올리며, $d = 1$이면 오른쪽으로, $d = -1$이면 왼쪽으로 움직인다. 그 시각에 그 좌표에 다른 개미가 있는 경우는 입력으로 주어지지 않는다.
• $p = 2$이면 좌표를 알고 싶은 개미의 번호 $i$가 이어진다. $i$는 $1$ 이상이고 그때까지 올라간 개미의 수 이하다. $t$초일 때 $i$번 개미의 좌표를 출력하라는 뜻이다.

입력은 $t$가 증가하는 순서로 주어지고, 두 동작의 $t$가 같은 경우는 없다.

$p = 2$인 동작마다 그 개미의 좌표를 한 줄에 하나씩 출력한다. 이 조건에서 질의 시각의 좌표는 항상 정수이므로 정수로 출력한다.