Migrated from Lutece 2939 Stack Merge

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在S国里，水平分布着 $n$ 个料堆容器，每一个料堆容器可以视为一个存储空间无限大的栈，编号分别为 $1,2,...,n$ 。起初，第 $i$ 个栈中存在着唯一的元素 $i$。

现在我们定义以下若干种操作：

1. 设置一个新的临时栈 $Temp\_Stack_t$ ，选择第 $k$ 个栈中的所有元素，依次将 $Stack_k$ 中的自顶向下的连续元素弹出并插入 $Temp\_Stack_t$ 。
2. 选择第 $p$ 个栈 $Stack_p$ ，将第 $t$ 个临时栈 $Temp\_Stack_t$ 中的元素依次弹出并插入 $Stack_p$ 。
3. 查询此时在 $Stack_1$ 到 $Stack_n$ 中空栈的个数。
4. 查询元素 $x$ 在 $x$ 所属的栈中的元素排名。其中栈内元素排名定义为自栈顶向下的元素计数，规定栈顶元素排名为1。

由于S国的限制，上述四个操作也存在一些限制：

1. 当一个栈为空后，该栈即拒绝接受任何元素进入，即无法再进行操作 2；
2. 每一次进行操作 4 的询问时，保证不存在一个临时栈中存在元素。

针对给出的m组操作，请你输出每组操作 3 与操作 4 对应的答案。

Input

第一行两个整数 $n, \ m$，表示初始栈的个数和操作个数。

接下来 $m$ 行，针对第 $i$ 行，首先读入操作种类 $opt$ ：

若 $opt = 1$ ，则接下来一个正整数 $k$ ，表示选择第 $k$ 个栈中的自顶向下所有的元素插入临时栈中，题面中的 $t$ 为这里操作的序号 $i$ 。

若 $opt = 2$， 则接下来两个正整数 $p, \ t$ ，表示将第 $t$ 个临时栈 $Temp\_Stack_t$ 中的元素插入 $Stack_p$ 。

若 $opt=3$ ，表示询问此时除去临时栈外的空栈的个数。

若 $opt=4$ ，则接下来一个正整数 $x$ ，表示询问 $x$ 在其栈中的排名。

Output

针对每个 $opt = 3$ 以及 $opt=4$ ，每行输出一个整数表示答案。

Samples

5 16
1 1
3
2 2 1
4 2
4 1
4 3
4 5
1 2
3
1 3
2 4 10
2 4 8
4 2
4 3
4 4
4 5

1
2
1
1
1
2
2
3
4
1

Constraints

$1\leq n \leq 10^6, \ 1\leq m \leq 2 \times 10^6$ ， $opt \in \{1,\ 2, \ 3, \ 4 \}$

$1 \leq k \leq n$

$1\leq p \leq n$ ，$1\leq t \leq m$ ，保证 $Stack_p$ 不为空且第 $t$ 个操作为操作 1

$1 \leq x \leq n$

Resources

2023 UESTC ICPC Training for Data Structures