A85984.「RCOI2019」维护

题目来源：「RCOI2019」Rochine Round 1

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

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

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

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

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

• 插入操作，格式为 1 x：

  • 首先，执行 $x\leftarrow x\ \mathrm{xor}\ \text{lastans}$；
  • 然后，增加一个编号为已经加入过的结点总数 $+1$ 的节点作为 $x$ 的儿子。
  • 若 $\text{online}=1$，则 $\text{lastans}$ 更新为 $x$，若 $x$ 已经被删除则不应新增任何节点。

• 删除操作，格式为 2 x：

  • 首先，执行 $x\leftarrow x\ \mathrm{xor}\ \text{lastans}$；
  • 然后删除 $x$，若不存在请忽略。
  • 若 $\text{online}=1$，则 $\text{lastans}$ 更新为 $x$ 的父亲，保证 $x\ne 1$。

• 查询操作，格式为 3 x y：

  • 首先，执行 $x\leftarrow x\ \mathrm{xor}\ \text{lastans}$，$y\leftarrow y\ \mathrm{xor}\ \text{lastans}$；
  • 然后输出 $x$ 的 $y$ 代祖先。
  • 若 $\text{online}=1$，则 $\text{lastans}$ 更新为答案，若 $x$ 被删除了则什么都不要输出，若不存在则答案为 $0$。

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

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

测试点编号	$q$	$\text{online}$	特殊性质	每测试点分数
$1\sim 3$	$20$	$1$	数据随机生成	$3$
$4,5$	$20$	$0$	数据随机生成	$3$
$6\sim 8$	$200$	$1$	数据随机生成	$3$
$9,10$	$200$	$0$	数据随机生成	$3$
$11,12$	$2\times 10^4$	$1$	数据随机生成	$3$
$13\sim 15$	$2\times 10^4$	$0$	数据随机生成	$3$
$16\sim 19$	$2\times 10^5$	$0$	无	$4$
$20$	$2\times 10^5$	$1$	无删除操作	$9$
$21\sim 25$	$2\times 10^5$	$1$	无	$6$

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