UOJ Logo

NOI.AC

1S 512MB

#2830. introduce a little anarchy

Statistics

饭点了,有 $m$ 个班总共 $n$ 名同学来食堂排队打饭。

正常的打饭队伍应该是一个严格的队列结构,但是今天的饭堂一片混乱。

同学们依然是排成一个队列,但是每次入队的时候,他们会找到位置最靠后的同班同学,随后排在他后面。

队伍依然只有头部可以出队,但是同学们有可能在出队后再返回队列中重新买饭。

具体来说,队伍支持两种操作:

push x:同学 $i$ 入队,如果前面有 $i$ 同学的同班同学,$i$ 会排在最后一个同班同学的后面。否则排到队尾。

pop:出队,队伍最前面的同学从队列中退出。

现在给出一系列的进出队操作,对于每次出队,请输出对应同学的编号。

同学和班级从 $0$ 开始编号。

输入格式

第一行两个整数 $n$ 和 $m$,分别表示同学个数和班级个数。

接下来每一行 $n$ 个非负整数 $A_i$,表示同学 $i$ 的班级。

接下来一行一个正整数 $T$,表示操作数目。

接下来 $T$ 行,每行一个操作。

输出格式

对于每个出队操作输出一行,表示出队的同学编号。

样例输入

输入 #1

4 2
0 0 1 1
6
push 2
push 0
push 3
pop
pop
pop

样例输出

输出 #1

2
3
0

数据范围

对于 $30\%$ 的数据,有 $1\leq n \leq 100, 1 \leq m \leq 10, 1\leq T \leq 50$。

对于 $100\%$ 的数据,有 $1\leq n \leq 10^5, 1\leq m\leq 300, 1\leq T\leq 10^5$。

输入保证操作合法。