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