给定一棵包含 n 个点的由有根树构成的森林(初始没有边,每个顶点是一棵有根树的根),顶点由 1 到 n 的整数编号表示。你需要维护森林的轻重链剖分结构,具体如下:
对每个顶点 ω(1≤ω≤n),记其孩子构成的集合为 children(ω)。对于每个 ω,若 ω 不是根,则记其父亲为 father(ω)。
一个顶点 ω 的子树规模 size(ω) 定义为 1+∑u∈children(ω)size(u)
一个顶点 ω 如果不是叶子(即 children(ω)≠∅),则它的重孩子 he(ω) 被定义为 argmaxu∈children(ω)size(u)⋅n+max(u,he(u),he(he(u)),⋯),即子树规模最大的孩子(若有多个孩子 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
之一,否则不进行操作。
- 在 [1,n] 中等概率随机选取三个整数 x,y,k,若 x,y 在不同的有根树上,则生成一行
- 性质 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,没有特殊限制。