题目描述

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

对每个顶点 $w\;(1\le w\le n)$，记其孩子构成的集合为 $\mathrm{children}(w)$，对 $w$ 若 $w$ 不是根则记其父亲为 $\mathrm{father}(w)$；

一个顶点 $w$ 的子树规模 $\mathrm{size(w)}$ 定义为 $1+\sum\limits_{u\in\mathrm{children}(w)}\mathrm{size(u)}$；

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

重链是一个由顶点构成的序列 $w_1,w_2,\dots,w_k\;(k>0)$，满足条件：

• $w_1$ 是根或 $w_1\ne \mathrm{hc}(\mathrm{father}(w_1))$
• $w_i=\mathrm{hc}(w_{i-1})\;(2\le i\le k)$

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

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

• 加边：给出两个顶点 $a,b$，令 $b$ 成为 $b$ 所在有根树的根（设顶点构成的序列 $t_1,t_2,\dots,t_l$ 满足 $t_l=b$，且 $t_1$ 为根，$(t_i,t_{i+1}),\;1\le 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) \mod N)+1$ 小的权值。

输入格式

第 $1$ 行有两个整数 n m ；

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

输出格式

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

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

1
5
2
7
7
6
7
2
1
7

提示

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

本题采用子任务评测。

共 $31$ 个测试点，所有测试点满足 $1\le n\le 10^5$，$1\le m\le 5\times 10^5$，$0\le o\le 1$，$1\le a\le n$，$1\le b \le n$，$1\le k\le 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\le i\le n$，数据的第 $i$ 行为 1 a i k，其中 $a$ 在 $[1,i-1]$ 中的整数等概率选取；

• 性质3：$m=n-1$，且对 $2\le i\le n$，数据的第 $i$ 行为 1 i b k，其中 $b$ 在 $[1,i-1]$ 中的整数等概率选取；

• 其它对 $n,m$ 的限制。

每个测试点的性质如下：

第1个测试点，$n=10,\;m=50$，满足性质1，共10分；

第2个测试点，$n=100,\;m=500$，满足性质1，共10分；

第3个测试点，$n=1000,\;m=5000$，满足性质1，共10分；

第4个测试点，满足性质2，共15分；

第5个测试点，满足性质3，共15分；

第6~10个测试点，满足性质1，共20分；

第11~31个测试点没有特殊限制，共20分。