题目描述

有$N$个盒子，编号为$1,2,\ldots,N$，还有$10^{100}$个球，编号为$1,2,\ldots,10^{100}$。初始时，第$i$个盒子中只有球$i$。

总共进行$Q$个操作。

有三种类型的操作：$1$，$2$和$3$。

类型$1$：将盒子$Y$中的所有内容放入盒子$X$中。保证$X \neq Y$。

1 $X$ $Y$

类型$2$：将球$k+1$放入盒子$X$中，这里$k$是盒子中所含球的当前总数。

2 $X$

类型$3$：报告包含球$X$的盒子编号。

3 $X$

约束条件

• 输入中所有值都是整数。
• $2 \leq N \leq 3 \times 10^5$
• $1 \leq Q \leq 3 \times 10^5$
• 对于每个类型$1$的操作，$1 \leq X,Y \leq N$，且$X \neq Y$。
• 对于每个类型$2$的操作，$1 \leq X \leq N$。
• 对于每个类型$3$的操作，球$X$在某个盒子中。
• 至少有一个类型$3$的操作。

输入

输入以以下格式从标准输入给出。
这里，$op_i$表示第$i$个操作。

$N$ $Q$ $op_1$ $op_2$ $\vdots$ $op_Q$

输出

对于每个类型$3$的操作，打印一行包含一个整数值的响应。

样例输入 1

5 10
3 5
1 1 4
2 1
2 4
3 7
1 3 1
3 4
1 1 4
3 7
3 6

样例输出 1

5
4
3
1
3

这个样例输入包含十个操作。

• 第一个操作是类型$3$。球$5$在盒子$5$中。
• 第二个操作是类型$1$。将盒子$4$的所有内容放入盒子$1$中。
  • 盒子$1$现在包含球$1$和$4$，盒子$4$现在为空。
• 第三个操作是类型$2$。将球$6$放入盒子$1$中。
• 第四个操作是类型$2$。将球$7$放入盒子$4$中。
• 第五个操作是类型$3$。球$7$在盒子$4$中。
• 第六个操作是类型$1$。将盒子$1$的所有内容放入盒子$3$中。
  • 盒子$3$现在包含球$1$、$3$、$4$和$6$，盒子$1$现在为空。
• 第七个操作是类型$3$。球$4$在盒子$3$中。
• 第八个操作是类型$1$。将盒子$4$的所有内容放入盒子$1$中。
  • 盒子$1$现在包含球$7$，盒子$4$现在为空。
• 第九个操作是类型$3$。球$7$在盒子$1$中。
• 第十个操作是类型$3$。球$6$在盒子$3$中。