字典树简单题

题号：NC233446
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有一棵 $n$ 个节点的 01 Trie。这棵 01 Trie 的根节点是 $1$ ，保证每一个叶子节点的深度都相同。
众所周知在 01 Trie 上可以快速的查询第 $k$ 小的元素。但是这样太简单了，于是稍微加强了一下，需要支持以下两种操作：

$1\ x\ s$ ：记目前 01 Trie 上节点的数量为 $p$ ， $s$ 是一个 01 串。新建 $|s|$ 个节点 $p+1,p+2,\cdots, p+|s|$ ，设下标从 $1$ 开始，长度为 $|s|+1$ 的序列 $q=[x,p+1,p+2,\cdots,p+|s|]$ ，对于 $i\in[1,|s|]$ ，从节点 $q_i$ 向 $q_{i+1}$ 连边，边权为 $s_i$ 。保证叶子节点 $p+|s|$ 的深度和其他叶子节点一致。通俗的讲，就是在节点 $x$ 为根的子 01 Trie 内，新增一个二进制表示为 $s$ 的数。

$2\ x\ k$ ：定义点 $x$ 到叶子节点 $y$ 的权值为 $x$ 到 $y$ 路径上数字依次拼接形成的二进制数。特别的，如果 $x$ 是一个叶子节点，那么 $x$ 到 $x$ 的权值为 $0$ 。求 $x$ 到所有叶子的权值中第 $k$ 小的叶子节点编号。

如果你不了解 01 Trie，可以在 OI wiki 了解它的相关定义：https://oi-wiki.org/string/trie/#_6。

输入描述:

本题强制在线。每次操作中的  都需要异或上一次的答案 。初始时 。
第一行三个正整数 ，表示这棵 01 Trie 的初始节点数量，操作次数，以及 01 Trie 的深度（根节点  的深度为 ）。
第二至第  行，第  行有两个整数 ，表示点  01 Trie 上的父亲节点为 ，这条边的边权为 。
接下来  行，每行表示一次修改操作或一次询问操作。具体输入格式如题目描述所述。
保证修改操作加入的节点数量不超过 ；01 Trie 上所有点的父亲编号小于自己的编号；根节点到任意节点的路径上二进制数不同；询问操作的  不大于目前叶子节点的数量；所有操作中通过计算得到真实的  一定在 01 Trie 上。

输出描述:

如果有  个询问操作，那么应该输出  行，其中第  行表示第  次询问的答案。

示例1

输入

复制

输出

复制

7
10