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

For each vertex $\omega$ ($1 \leq \omega \leq n$), let $\mathrm{children}(\omega)$ be the set of its children. For each $\omega$, if $\omega$ is not a root, let $\mathrm{father}(\omega)$ be its parent.

The subtree size $\mathrm{size}(\omega)$ of a vertex $\omega$ is defined as $1 + \displaystyle\sum_{u \in \mathrm{children}(\omega)} \mathrm{size}(u)$.

If a vertex $\omega$ is not a leaf (i.e., $\mathrm{children}(\omega) \ne \varnothing$), its heavy child $\mathrm{he}(\omega)$ is defined as $\displaystyle \arg \max_{u \in \mathrm{children}(\omega)} \mathrm{size}(u) \cdot n + \max(u, \mathrm{he}(u), \mathrm{he}(\mathrm{he}(u)), \cdots)$, which 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 $\omega_1, \omega_2, \cdots, \omega_k$ ($k > 0$) satisfying the conditions:

• $\omega_1$ is a root or $\omega_1 \ne \mathrm{he}(\mathrm{father}(\omega_1))$
• $\omega_i = \mathrm{he}(\omega_{i-1})$ for $2 \leq i \leq k$

In any tree, each vertex belongs to exactly one heavy chain. The weight of a heavy chain is $\omega_1 \oplus \omega_2 \oplus \cdots \oplus \omega_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:

• Add edge: Given two vertices $a, b$, make $b$ the root of the tree it belongs to (if the sequence of vertices $t_1, t_2, \cdots, t_l$ satisfies $t_l = b$ and $t_1$ is the root, with $(t_i, t_{i+1})$ being directed edges on the tree, reverse these edges to $(t_{i+1}, t_i)$ to make $b$ the root), then add a directed edge $(a, b)$ from $a$ to $b$. It is guaranteed that $a$ and $b$ are in different rooted 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 total number of heavy chains. Find the weight of the $((k-1) \bmod N)+1$-th smallest heavy chain when all current heavy chains are sorted by their weights in ascending order.

Input

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 edge $a, b$ and then query $k$. If $o=0$, it means first remove edge $a, b$ and then query $k$.

Output

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

Examples

Input 1

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

Output 1

4
5
7
4
6
6
6
4
5
4

Subtasks

There are 31 test cases in total. All test cases satisfy $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$, 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:
  • Randomly select three integers $x, y, k$ uniformly 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, randomly 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 \leq i \leq n$, the $i$-th line of data is 1 a i k, where $a$ is chosen uniformly from $[1, i-1]$.
• Property 3: $m=n-1$, and for $2 \leq i \leq n$, the $i$-th line of data is 1 i b k, where $b$ is chosen uniformly from $[1, i-1]$.

The properties for each test case are as follows:

• Subtask 1 (5 points): Test case 1, $n=10, m=50$, satisfies Property 1.
• Subtask 2 (5 points): Test case 2, $n=100, m=500$, satisfies Property 1.
• Subtask 3 (10 points): Test case 3, $n=1\,000, m=5\,000$, satisfies Property 1.
• Subtask 4 (10 points): Test case 4, satisfies Property 2.
• Subtask 5 (10 points): Test case 5, satisfies Property 3.
• Subtask 6 (20 points): Test cases 6-10, satisfy Property 1.
• Subtask 7 (40 points): Test cases 11-31, no special restrictions.