题目描述

维护一颗以 $1$ 为根的树的形态，要求支持插入叶子节点、删除任意结点以及查询 $k$ 代祖先。为了尽量简单，删除时，直接让这个点的儿子替代它就好（即，全部接到父节点上）。初始时，树仅有根节点 $1$。

输入格式

第一行两个整数 $q$ 和 $online$。$q$ 表示操作数，$online=1$ 说明本测试点强制在线。

请认真阅读下面的输入格式，稍有不慎即会 WA。

对于三种操作， 若询问的 $x$ 已经被删除或 $x>$ 节点总数或 $x=0$，则 $lastans$ 也不要更新。

接下来 $q$ 行，分为三种情况（$lastans$ 初值为 $0$）：

• 插入操作，格式为 1 x。
  • 首先，执行 $x\leftarrow x\ \mathrm{xor}\ lastans$；
  • 然后，增加一个编号为已经加入过的结点总数 $+1$ 的节点作为 $x$ 的儿子。
  • 若 $online=1$，则 $lastans$ 更新为 $x$，若 $x$ 已经被删除则不应新增任何节点。
• 删除操作，格式为 2 x。
  • 首先，执行 $x\leftarrow x\ \mathrm{xor}\ lastans$；
  • 然后删除 $x$，若不存在请忽略。
  • 若 $online=1$，则 $lastans$ 更新为 $x$ 的父亲，保证 $x\ne 1$；
• 查询操作，格式为 3 x y。
  • 首先，执行 $x\leftarrow x\ \mathrm{xor}\ lastans$，$y\leftarrow y\ \mathrm{xor}\ lastans$；
  • 然后输出 $x$ 的 $y$ 代祖先。
  • 若 $online=1$，则 $lastans$ 更新为答案，若 $x$ 被删除了则什么都不要输出，若不存在则答案为 $0$。

输出格式

输出一些行，每行一个整数，表示询问的答案。

样例

样例输入 1

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

样例输出 1

2
1
0

样例输入 2

9 0
1 1
1 2
1 3
1 4
2 2
2 3
3 4 1
3 5 2
3 4 0

样例输出 2

1
1
4

样例输入 3

4 0
1 1
2 2
3 2 0
3 1 0

样例输出 3

1

样例输入 4

20 1
1 1
1 3
1 1
3 7 1
3 6 1
3 5 3
1 6
1 1
1 1
1 3
3 15 1
3 8 3
3 11 2
1 1
1 14
1 0
1 3
3 7 10
3 7 8
3 11 5

样例输出 4

2
1
2
0
3
7
11
7
8

数据范围

对于所有数据，$1\le q\le 2\times 10^5,\text{online}\in\{0,1\}$。详细数据范围如下。

对于 $q\le 2\times 10^4$ 的测试点，按点计分；其他测试点，按特殊性质对应 Subtask 捆绑计分。