QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 8704. 排队

Statistics

有若干个人排队,一开始队列是空的,在第 $t(t=1,2,\cdots,n)$ 个时刻发生了如下的事件之一:

  1. $x$:新增了一个人,他的编号顺延,他站在编号为 $x$ 的人后面($x=0$ 表示在队伍开头)。
  2. $i,y$:设编号为 $i$ 的人进入队伍的时间为 $t'$,则修改 $t'$ 时刻的操作为 $1\ y$
    • 修改操作会影响 $t'$ 时刻之后的所有操作。
  3. $z$:查询此时编号为 $z$ 的人站在队伍的第几个位置。

Input

一行两个数 $sub,n$ 表示子任务标号和操作数量。

然后 $n$ 行,每行先输入一个数 $opt$ 表示操作类型。

若 $opt=1$,则输入一个数 $x$。

若 $opt=2$,则输入两个数 $i,y$。

若 $opt=3$ ,则输入一个数 $z$。

保证所有操作以及修改后的操作发生时涉及的人已经在队列中。

Output

对于每一个 $3$ 操作,输出一行一个数表示位置。

Example

Input

0 8
1 0
1 1
1 2
3 2
2 2 0
3 1
3 2
3 3

Output

2
3
1
2

Notes

样例解释:

第三个操作结束后队列为 $1,2,3$。

第五个操作结束后队列为 $2,3,1$。

Scoring

对于所有测试数据,保证 $1\leq n\leq 300000$,$x,i,y,z$ 合法。

$\text{Subtask0, 4pts: }n\leq 500$。

$\text{Subtask1, 19pts: }opt \ne 2$。

$\text{Subtask2, 21pts: }$ 保证操作 $3$ 的个数不超过 $200$。

$\text{Subtask3, 23pts: }$ $opt,x,i,y,z$ 依次在合法范围内均匀随机生成。

$\text{Subtask4, 33pts: }$ 无特殊限制。