Problem Description

You are given a forest consisting of rooted trees with $n$ vertices (initially there are no edges, and each vertex is the root of a rooted tree). The vertices are labeled with integers from $1$ to $n$.

You need to maintain the Heavy-Light Decomposition (HLD) structure of the forest, defined as follows:

For each vertex $w\;(1\le w\le n)$, let the set of its children be $\mathrm{children}(w)$. If $w$ is not a root, let its parent be $\mathrm{father}(w)$.

The subtree size of a vertex $w$, denoted $\mathrm{size}(w)$, is defined as $1+\sum\limits_{u\in\mathrm{children}(w)}\mathrm{size}(u)$.

If a vertex $w$ is not a leaf (i.e., $\mathrm{children}(w)\ne\varnothing$), then its heavy child $\mathrm{hc}(w)$ is defined as $\mathrm{arg}\max_{u\in\mathrm{children}(w)}size(u)\cdot n+\max(u,\mathrm{hc}(u),\mathrm{hc}(\mathrm{hc}(u)),\dots)$. That is, it is the child with the largest subtree size. If there are multiple children $u$ with the same subtree size, choose the one whose heavy chain (within the subtree rooted at $u$) contains the largest maximum vertex label.

A heavy chain is a sequence of vertices $w_1,w_2,\dots,w_k\;(k>0)$ satisfying:

• $w_1$ is a root, or $w_1\ne \mathrm{hc}(\mathrm{father}(w_1))$.
• $w_i=\mathrm{hc}(w_{i-1})\;(2\le i\le k)$.

In a tree, each vertex belongs to exactly one heavy chain.

The weight of a heavy chain is $w_1\oplus w_2\oplus\dots\oplus w_k$, i.e., the bitwise XOR of the vertex labels in the sequence.

You need to perform $2m$ operations in order. The operations are:

• Add edge: given two vertices $a,b$, make $b$ the root of the rooted tree containing $b$ (let the sequence of vertices $t_1,t_2,\dots,t_l$ satisfy $t_l=b$, $t_1$ is the root, and $(t_i,t_{i+1}),\;1\le i<l$ are directed edges in the rooted tree containing $b$; reverse these edges to $(t_{i+1},t_i)$ to make $b$ the root). Then add the directed edge $(a,b)$. It is guaranteed that before this operation, $a$ and $b$ are in different rooted trees.
• Delete edge: given two vertices $a,b$, delete the directed edge between $a$ and $b$ (it may be $(a,b)$ or $(b,a)$). It is guaranteed that this edge existed before.
• Query: given an integer $k$, suppose there are currently $N$ heavy chains. Sort all existing heavy chains by their weights in increasing order, and ask for the $((k-1) \mod N)+1$-th smallest weight.

Input Format

The first line contains two integers n m.

The next $m$ lines each contain four integers o a b k. If $o=1$, it means first add the edge $a,b$, then query $k$. If $o=0$, it means first delete the edge $a,b$, then query $k$.

Output Format

Output $m$ lines, each containing one integer, in order, which are the results of each query.

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

Hint

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

This problem uses subtask-based judging.

There are $31$ test points. All test points satisfy $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$, and $n,m,o,a,b,k$ are all integers.

The testdata may have the following properties:

• Property 1: The operations are generated randomly using the following strategy, repeated until an operation sequence of $m$ lines is generated:

• Uniformly choose three integers $x,y,k$ in $[1,n]$. If $x,y$ are in different rooted trees, generate a line 1 x y k. Otherwise, if $x$ is not a root, uniformly generate one of 0 x father(x) k or 0 father(x) x k. Otherwise, do nothing.

• Property 2: $m=n-1$, and for $2\le i\le n$, the $i$-th line of the testdata is 1 a i k, where $a$ is chosen uniformly from the integers in $[1,i-1]$.

• Property 3: $m=n-1$, and for $2\le i\le n$, the $i$-th line of the testdata is 1 i b k, where $b$ is chosen uniformly from the integers in $[1,i-1]$.

• Other constraints on $n,m$.

The properties of each test point are:

Test point 1: $n=10,\;m=50$, satisfies Property 1, 10 points.

Test point 2: $n=100,\;m=500$, satisfies Property 1, 10 points.

Test point 3: $n=1000,\;m=5000$, satisfies Property 1, 10 points.

Test point 4: satisfies Property 2, 15 points.

Test point 5: satisfies Property 3, 15 points.

Test points 6 to 10: satisfy Property 1, 20 points.

Test points 11 to 31: no special constraints, 20 points.

Translated by ChatGPT 5