2313: 老师叫你搬东西
[Creator : ]
Description
有$n$个人排队，1号排在 2号前面，2号排在 3号前面，...，以此类推 $n-1$ 号排在 $n$ 号前面。在这个过程中，偶尔老师会把某个人叫走帮忙搬书，叫走之后这个人就离开了队伍，假设本来a排在b前面，b排在 c前面，b被叫走后 a 就排在了 c前面。老师偶尔也会感到疑问，她想知道此时排在a号前面的同学是几号呢？
已知老师一共会有k次操作，每次会执行下面的一种：
已知老师一共会有k次操作，每次会执行下面的一种：
- 1.把 x叫走。
- 2.求排在x前面的是谁。
Input
第一行输入两个正整数n，k (1<=n,k<=1e6)。n 表示排队人数，k 表示老师的操作次数。
接下来 k行，每行包含2个整数，表示一个操作，具体如下：
1 x ：把 x 叫走，保证此时 x一定在队伍里
2 x：输出排在 x前面的人的编号，保证此时 x 一定在队伍里，如果没有人排在 x 前面，输出 0 。
(1≤x≤n)
接下来 k行，每行包含2个整数，表示一个操作，具体如下：
1 x ：把 x 叫走，保证此时 x一定在队伍里
2 x：输出排在 x前面的人的编号，保证此时 x 一定在队伍里，如果没有人排在 x 前面，输出 0 。
(1≤x≤n)
Output
输出包含若干行整数，即为所有操作2的结果。 Sample Input Copy
5 4
2 1
1 3
2 5
2 4
Sample Output Copy
0
4
2
HINT
1<=n,k<=106