Uolevi has $n$ tiles each consisting of a single integer from $1$ to $n$. Since he likes working with ceramics, he wants to combine these tiles into a tile he thinks is more artistic. But when firing a tile, it might break if it contains too many small integers. So Uolevi sometimes wants to know how many small integers a tile contains. To prevent breaking, Uolevi might need to split a tile into two tiles, the other containing smaller and the other larger integers.

More specifically, Uolevi wants to perform three types of queries:

• $1$ $i$ $j$: Combine tiles indexed $i$ and $j$ into a single tile with index $i$. It is guaranteed that tiles with indexes $i$ and $j$ exist.
• $2$ $i$ $j$ $k$ Split the tile with index $i$ into two tiles $i$ and $j$, such that tile $i$ contains the $k$ smallest integers from the original tile, and the other tile contains the rest. It is guaranteed that both resulting tiles will be nonempty, a tile with index $i$ exists, and no tile with index $j$ exists.
• $3$ $i$ $x$: How many integers in tile $i$ are at most $x$? It is guaranteed that a tile with index $i$ exists.

Initially every integer is in its own tile, and the index of integer $i$'s tile is $i$.

Input

The first line contains two integers $n$ $q$: The amount of integers and queries.
$q$ lines follow, each being a query of one of the three types as described above:

• $1$ $i$ $j$
• $2$ $i$ $j$ $k$
• $3$ $i$ $x$

Output

Output the answer to every query of type $3$.

Constraints

• $1 \leq n, q \leq 4 * 10^{5}$
• $1 \leq i, j, x \leq n$

Example

Input:

4 8
1 1 3
1 2 4
3 1 2
3 2 1
1 1 2
3 1 3
2 1 4 2
3 4 4

Output:

1 0 3 2