有若干个人排队，一开始队列是空的，在第 $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: }$ 无特殊限制。