Dynamic Heavy Chain Decomposition

You are given a forest of n nodes (numbered 1 through n), where initially each node forms a rooted tree by itself. You need to dynamically maintain a heavy‐chain decomposition of the forest under a series of operations. In each tree, for every vertex w (1 ≤ w ≤ n), denote its children by children(w) (if w is not a root, its parent is father(w)). The size of the subtree of w is defined as

[ \mathrm{size}(w)=1+\sum_{u\in\mathrm{children}(w)}\mathrm{size}(u),. ]

For a non‐leaf vertex w (i.e. children(w)\neq\varnothing), its heavy child hc(w) is defined as the child u which maximizes

[ \mathrm{size}(u)\times n+\max\Bigl({u,,hc(u),,hc(hc(u)),\dots}\Bigr),. ]

That is, among children with the largest subtree size, choose the one whose heavy chain (the chain starting at that child by repeatedly following heavy child pointers) contains the maximum vertex (by label). A heavy chain is a sequence of vertices w₁,w₂,…,w_k (k > 0) satisfying:

• w₁ is either a root or w₁ \neq hc(father(w₁)),
• For every 2 ≤ i ≤ k, we have w_i = hc(w_i-1).

Every vertex belongs to exactly one heavy chain. The weight of a heavy chain is defined as the bitwise XOR of all vertex numbers in the chain:

[ \mathrm{weight}(chain)=w_1\oplus w_2\oplus\dots\oplus w_k,. ]

You are to process exactly 2m operations. Each operation is one of the following types:

• Add edge: Given two vertices a and b, first modify the tree that contains b so that b becomes its root. (To achieve this, consider the unique path t₁,t₂,…,t_l in the tree containing b with t_l = b and t₁ as the root, and reverse every edge on that path.) Then add a directed edge from a to b (i.e. set b as a child of a). It is guaranteed that a and b were in different trees before the operation.
• Delete edge: Given two vertices a and b, remove the directed edge connecting them (the edge can be either (a,b) or (b,a)). It is guaranteed that such an edge exists prior to deletion.
• Query: Given an integer k, let there be N heavy chains in the current forest. Sort all heavy chain weights in increasing order and output the weight at position ((k-1) mod N)+1 (1-indexed).

Note: All formulas are given in LaTeX format and the input guarantees that the operations are valid.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤  some bound, m ≥ 1), where the total number of operations is exactly 2m.

Each of the next 2m lines describes an operation in one of the following formats:

• 1 a b — Add edge operation. Here, a and b are two distinct vertices in different trees.
• 2 a b — Delete edge operation. There is guaranteed to be an edge between a and b before this operation.
• 3 k — Query operation. Outputs the heavy chain weight that is the ((k-1) mod N)+1-th smallest among all heavy chains.

It is guaranteed that the operations are valid.

outputFormat

For each query operation (operation type 3), output a single line containing the answer.

sample

5 2
1 1 2
3 1
1 2 3
3 2

3
4

</p>