통로 위의 개미 Batch 컴파일 명령

길이가 L인 선분 형태의 통로가 있다. 경근이는 통로를 원활하게 관리하기 위해, 도로에 좌표를 도입했다. 도로의 왼쪽 끝점의 좌표는 0이고, 도로의 오른쪽 끝점의 좌표는 L이며, 도로를 x : y로 내분하는 점의 좌표는 이다.

이제 경근이는 심심할 때마다 개미를 통로 위에 한 마리씩 올릴 것이다. 경근이의 통로는 매우 신비로워서, 어떤 개미라도 경근이의 통로 위에 올라가기만 하면 반드시 오른쪽이나 왼쪽 방향으로 1초에 1의 거리를 움직인다. 통로의 폭은 최대 한 마리의 개미만이 움직일 수 있을 정도로 매우 좁아서, 서로 반대방향으로 움직이는 개미들이 어느 한 위치에서 부딪치면 그 즉시 두 개미 모두 방향을 반대로 바꾸어 원래의 속력을 유지하며 움직인다. 개미가 통로의 양 끝점에 도달할 때에도 그 즉시 방향을 반대로 바꾸어 원래의 속력을 유지하며 움직인다. 개미의 크기는 매우 작아서 점으로 취급하여, 두 개미는 정확히 같은 위치에 존재해야 부딪히고, 정확히 통로의 끝점에 가야 방향을 바꾼다고 생각하자.

처음의 시각을 0초로 두자. 0초에는 통로 위에 개미가 한 마리도 없다. 여러분은 다음과 같은 동작을 Q번 처리하는 프로그램을 작성해야 한다.

1. t초에 통로의 위치가 x인 지점 위에 오른쪽 또는 왼쪽으로 움직이는 개미를 올린다. 이 개미가 i번째로 올려졌다면, 이 개미에 번호 i를 부여한다.
2. t초일 때 i번 개미의 좌표를 출력한다.

입력

첫 번째 줄에 두 자연수 L과 Q (1 ≤ L ≤ 10⁹, 1 ≤ Q ≤ 2×10⁵)가 주어진다.

다음 Q개의 줄에는 프로그램이 처리해야 할 동작들이 한 줄에 하나씩 주어진다. 각 줄의 입력 형식은 아래와 같다.

• 먼저 동작을 하는 시점을 나타내는 정수 t(0 ≤ t ≤ 10¹⁸)와 동작의 종류를 나타내는 자연수 p(1 ≤ p ≤ 2)가 공백을 사이로 두고 주어진다.
  • p = 1이면 개미가 올라가는 위치를 나타내는 정수 x(0 < x < L)와 개미가 움직이는 방향을 나타내는 정수 d ()가 공백을 사이로 두고 주어진다. 이는 t초일 때 x번 위치에 d = 1이면 오른쪽으로, d = -1이면 왼쪽으로 움직이는 개미를 올린다는 의미이다. 이 위치에 다른 개미가 이미 있는 경우는 입력으로 주어지지 않는다.
  • p = 2이면 위치를 알고 싶은 개미의 번호 i (1 ≤ i ≤ (현재 까지 올라간 개미 수))가 공백을 사이로 두고 주어진다. 이는 t초에 i번 개미의 좌표를 출력하라는 의미이다.

t의 값이 증가하는 순서대로 입력이 주어지며(즉 시간 순으로 입력이 주어진다), 두 동작이 같은 t를 가지는 경우는 없다(같은 시각에 두 가지 이상의 동작을 처리할 일은 없다).

출력

p = 2인 동작을 처리할 때마다, 각 줄에 문제에서 요구하는 답(개미의 좌표)을 출력한다.

부분문제

입출력 예제