셔틀버스

교내를 도는 셔틀버스에는 한쪽 벽을 따라 좌석 $N$개가 일렬로 놓여 있다. 가장 왼쪽 좌석이 1번, 가장 오른쪽 좌석이 $N$번이다. 버스는 정문에서 학생 $N$명을 태우고 출발하고, 학생들은 각자 좌석 하나를 골라 앉는다. 출발할 때 $i$번 좌석에 앉은 학생을 $i$번 학생이라고 부른다.

학생들은 칸막이에 기대어 조는 것을 좋아해서 되도록 양쪽 끝자리에 앉고 싶어 한다. 그래서 바로 옆 학생이 내리거나 다른 자리로 옮겨서 그 좌석이 비었을 때, 그 좌석으로 옮기면 1번 좌석과 $N$번 좌석 중 더 가까운 좌석까지의 거리가 줄어드는 경우 그 좌석으로 옮겨 앉는다. $j$번 좌석의 거리는 $\min(j-1,\ N-j)$이다. 한 학생이 버스에서 내리는 즉시 더 옮길 학생이 없을 때까지 모든 학생이 이 규칙대로 움직인다.

기사 찬수는 지금 어느 좌석에 누가 앉아 있는지 궁금하다. 찬수를 위해 아래 두 연산을 입력 순서대로 처리하는 프로그램을 작성하자.

1. 1 x : $x$번 학생이 버스에서 내린다. 이 학생이 버스에 타고 있음이 보장된다.
2. 2 x : $x$번 좌석에 앉은 학생의 번호를 출력한다. 좌석이 비어 있으면 0을 출력한다.

이 버스는 차고지로 들어가는 길이라 새로 타는 학생은 없다.

첫째 줄에 좌석의 수 $N$과 처리할 연산의 수 $M$이 공백을 사이에 두고 주어진다. ($1 \le N \le 200\,000$, $1 \le M \le 400\,000$)

둘째 줄부터 $M$개의 줄에 각 연산의 종류(1 또는 2)와 $x$가 공백을 사이에 두고 주어진다. ($1 \le x \le N$) 2번 연산은 적어도 하나 주어진다.

각 2번 연산의 결과를 입력 순서대로 한 줄에 하나씩 출력한다.

다음 그림은 좌석이 6개인 버스에서 학생이 차례로 내릴 때 자리가 어떻게 바뀌는지 보여 준다.

1번 학생이 내리면 2번 학생과 3번 학생이 차례로 왼쪽으로 옮긴다. 4번 학생은 3번 좌석으로 옮겨 앉아도 양 끝 좌석까지의 거리가 그대로여서 움직이지 않는다.

3번 학생이 내리면 4번 학생은 2번 좌석으로 가는 편이 이득이지만, 바로 옆자리가 아니므로 움직이지 않는다.

5번 학생이 내리면 4번 학생이 오른쪽으로 옮긴다.