980. 食堂排队
时间限制：1000 MS 内存限制：512 MB
题目描述
## 题目描述 又到了吃饭时间。小火龙来当食堂门口，看到长长的队伍，他的第一反应是看看有没有自己班里的同学，如果有的话，就插到他们前面去。 请你通过程序，模拟排队（插队）打饭的过程。 有 $n$ 个同学已经排好队了，班级相同的同学会排在一起。接下来会发生 $m$ 件事情，每件事情属于下面两个之一： - 1 x y：表示编号为 $x$，班级号为 $y$ 的同学，要过来排队了。如果队伍中有其他班级号为 $y$ 的同学，他就会站到他们前面去，否则站在队伍最后面。 - 2 表示队伍最前面的同学已经打好饭了，你需要输出他的编号。 ## 输入格式 第一行，一个整数 $n$ 和 $k$，表示已经有 $n$ 个人排好队伍了，表示总共的班级数，班级编号为 $1 \sim k$。 接下来 $n$ 行，每行两个整数 $a$ 和 $b$ ，表示从队头到队尾，每个学生的编号和班级号。 第 $n+2$ 行，一个整数 $m$，表示接下来发生的事情。 接下来 $m$ 行，表示每件事情。 ## 输出格式 在 $m$ 个事件中，对于每个“`2`”事件，输出当前学生的编号。 ## 数据范围 $50\%$ 的数据，$k=1$ ， 对于 $100\%$ 的，$n$ 和 $m$ 的范围 $[1,500000]$, $k$ 的范围 $[1,100000]$，学生的编号范围 $[1,10^8]$; 数据保证，进行 “`2`” 事件时，队伍里一定有人，并且离开队伍的人不会再回来了。 ## 输入 ```in1 5 4 1 1 2 1 3 2 4 2 5 3 10 1 6 1 2 1 7 4 1 8 2 1 9 3 1 10 4 2 ``` ## 输出 ```out1 6 1 2 8 3 ``` ## 提示