给定一棵包含 $n$ 个点的由有根树构成的森林（初始没有边，每个顶点是一棵有根树的根），顶点由 $1$ 到 $n$ 的整数编号表示。你需要维护森林的轻重链剖分结构，具体如下：

对每个顶点 $\omega$（$1 \leq \omega \leq n$），记其孩子构成的集合为 $\mathrm{children}(\omega)$。对于每个 $\omega$，若 $\omega$ 不是根，则记其父亲为 $\mathrm{father}(\omega)$。

一个顶点 $\omega$ 的子树规模 $\mathrm{size}(\omega)$ 定义为 $1 + \displaystyle\sum_{u \in \mathrm{children}(\omega)} \mathrm{size}(u)$

一个顶点 $\omega$ 如果不是叶子（即 $\mathrm{children}(\omega) \ne \varnothing$），则它的重孩子 $\mathrm{he}(\omega)$ 被定义为 $\displaystyle \arg \max_{u \in \mathrm{children}(\omega)} \mathrm{size}(u) \cdot n + \max(u, \mathrm{he}(u), \mathrm{he}(\mathrm{he}(u)), \cdots)$，即子树规模最大的孩子（若有多个孩子 $u$ 的子树规模相同，则取以 $u$ 为根的子树中，$u$ 所在的重链中最大的编号最大）；

重链是一个由顶点构成的序列 $\omega_1, \omega_2, \cdots, \omega_k(k > 0)$，满足条件：

• $\omega_1$ 是根或 $\omega_1 \ne \mathrm{he}(\mathrm{father}(\omega_1))$
• $\omega_i = \mathrm{he}(\omega_{i-1}) (2 \leq i \leq k)$

对一棵树，每个顶点恰好属于一条重链。重链的权值为 $\omega_1 \oplus \omega_2 \oplus \cdots \oplus \omega_k$，即序列中顶点编号的按位异或和。

需要依次进行 $2m$ 次操作，操作类型如下：

• 加边：给出两个顶点 $a, b$，令 $b$ 成为 $b$ 所在有根树的根（设定点构成的序列 $t_1, t_2, \cdots, t_l$ 满足 $t_l = b$ 且 $t_1$ 为根，$(t_i, t_{i+1}), 1 \leq i < l$ 是 $b$ 所在有根树上的有向边，将这些边反转为 $(t_{i+1}, t_i)$ 即可令 $b$ 成为根），然后加入 $a$ 到 $b$ 的有向边 $(a, b)$，保证操作前 $a,b$ 在不同的有根树上。
• 删边：给出两个顶点 $a, b$，删除 $a, b$ 间的有向边（可能为 $(a, b)$ 或 $(b, a)$），保证这条边之前存在。
• 查询：给出一个整数 $k$，设当前共有 $N$ 条重链，询问当前存在的所有重链按权值从小到大排序后，第 $((k-1) \bmod N)+1$ 小的权值。

输入格式

第一行有两个整数 $n, m$；

接下来 $m$ 行，每行四个整数 $o\;a\;b\;k$，若 $o=1$ 则表示先加边 $a, b$ 然后查询 $k$，若 $o=0$ 则表示先删边 $a,b$ 然后查询 $k$。

输出格式

共 $m$ 行，每行一个整数，依次为每次查询操作的结果。

样例数据

样例输入

5 10
1 1 2 3
1 2 3 3
1 2 4 3
1 3 5 3
0 2 3 3
1 1 3 3
0 1 2 3
1 2 3 3
0 3 5 3
1 1 5 3

样例输出

4
5
7
4
6
6
6
4
5
4

子任务

共 $31$ 个测试点，所有测试点满足 $1 \leq n \leq 10^5$，$1 \leq m \leq 5 \times 10^5$，$0 \leq o \leq 1$，$1 \leq a,b,k \leq n$，$n,m,o,a,b,k$ 均为整数。

测试点可能具有以下性质：

• 性质 1：操作使用以下策略随机生成，重复直到生成了 $m$ 行的操作序列。
  • 在 $[1,n]$ 中等概率随机选取三个整数 $x,y,k$，若 $x,y$ 在不同的有根树上，则生成一行 1 x y k，否则若 $x$ 不是根，等概率地生成一行 0 x father(x) k 或 0 father(x) x k 之一，否则不进行操作。
• 性质 2：$m=n-1$，且对 $2 \leq i \leq n$，数据的第 $i$ 行为 1 a i k，其中 $a$ 在 $[1,i-1]$ 中的整数等概率选取。
• 性质 3：$m=n-1$，且对 $2 \leq i \leq n$，数据的第 $i$ 行为 1 i b k，其中 $b$ 在 $[1,i-1]$ 中的整数等概率选取。

每个测试点的性质如下。

• 子任务 1（5 分）：测试点 1，$n=10, m=50$，满足性质 1。
• 子任务 2（5 分）：测试点 2，$n=100, m=500$，满足性质 1。
• 子任务 3（10 分）：测试点 3，$n=1\,000, m=5\,000$，满足性质 1。
• 子任务 4（10 分）：测试点 4，满足性质 2。
• 子任务 5（10 分）：测试点 5，满足性质 3。
• 子任务 6（20 分）：测试点 6-10，满足性质 1。
• 子任务 7（40 分）：测试点 11-31，没有特殊限制。