Given a forest of $n$ rooted trees (initially with no edges, where each vertex is the root of its own tree), the vertices are labeled with integers from $1$ to $n$. You need to maintain the heavy-light decomposition structure of the forest as follows:

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

The subtree size $\mathrm{size(w)}$ of a vertex $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$), 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 multiple children $u$ have the same subtree size, choose the one where the maximum vertex label in the heavy chain starting at $u$ is the largest).

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

• $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)$

For any tree, every vertex belongs to exactly one heavy chain. The weight of a heavy chain is $w_1\oplus w_2\oplus\dots\oplus w_k$, which is the bitwise XOR sum of the vertex labels in the sequence.

You need to perform $2m$ operations in sequence, where each operation is one of the following types:

• Add edge: Given two vertices $a, b$, make $b$ the root of the tree it currently belongs to (let the sequence of vertices $t_1, t_2, \dots, t_l$ satisfy $t_l=b$, where $t_1$ is the root and $(t_i, t_{i+1}),\;1\le i< l$ are the directed edges in the tree containing $b$; reversing these edges to $(t_{i+1}, t_i)$ makes $b$ the root), then add a directed edge $(a, b)$ from $a$ to $b$. It is guaranteed that $a$ and $b$ are in different trees before this operation.
• Remove edge: Given two vertices $a, b$, remove the directed edge between $a$ and $b$ (which could be $(a, b)$ or $(b, a)$). It is guaranteed that this edge exists.
• Query: Given an integer $k$, let $N$ be the current number of heavy chains. Find the $((k-1) \mod N)+1$-th smallest weight among all current heavy chains when sorted in ascending order.

Input

The first line contains two integers n and m.

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

Output

A total of m lines, each containing an integer, representing the result of each query operation in order.

Examples

Input 1

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

Output 1

1
5
2
7
7
6
7
2
1
7

Subtasks

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

This problem uses subtask-based evaluation.

There are 31 test cases in total. All test cases 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.

Test cases may have the following properties:

• Property 1: Operations are generated randomly using the following strategy, repeated until $m$ lines of operations are generated:
• Select three integers $x, y, k$ uniformly at random from $[1, n]$. If $x$ and $y$ are in different rooted trees, generate a line 1 x y k. Otherwise, if $x$ is not a root, generate either 0 x father(x) k or 0 father(x) x k with equal probability. Otherwise, perform no operation.
• Property 2: $m=n-1$, and for $2\le i\le n$, the $i$-th line of data is 1 a i k, where $a$ is selected uniformly at random from $[1, i-1]$.
• Property 3: $m=n-1$, and for $2\le i\le n$, the $i$-th line of data is 1 i b k, where $b$ is selected uniformly at random from $[1, i-1]$.
• Other constraints on $n, m$ apply.

The properties of each test case are as follows:

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

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

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

Test case 4: Satisfies Property 2, 15 points.

Test case 5: Satisfies Property 3, 15 points.

Test cases 6~10: Satisfy Property 1, 20 points.

Test cases 11~31: No special restrictions, 20 points.