Little Y has a large forest containing $n$ trees, numbered from $1$ to $n$. Initially, these trees are just saplings, each consisting of only a single node labeled $1$. Each of these trees has a special node, which we call the "growth node," that has the ability to sprout child nodes.

Little Y has mastered a magic spell that can cause the growth nodes of trees from $l$ to $r$ to sprout a child node. She can also change the growth node of trees from $l$ to $r$.

She has given you a record of her magic spells. Can you manage her forest and answer her queries?

Input

The first line contains two positive integers $n$ and $m$, representing the number of trees and the number of operations, respectively.

The next $m$ lines each contain several non-negative integers representing an operation. The formats are as follows:

1. 0 l r: This indicates that the growth nodes of trees from $l$ to $r$ sprout a child node. The label of the new child node is the label of the child node created by the previous type-0 operation plus $1$ (for example, the child node created by the first type-0 operation is labeled $2$). The nodes sprouted by trees from $l$ to $r$ have the same label. It is guaranteed that $1 \le l \le r \le n$.
2. 1 l r x: This indicates that the growth nodes of trees from $l$ to $r$ are changed to the node with label $x$. For a tree $i$ ($l \le i \le r$), if the node with label $x$ does not exist in it, this operation has no effect on that tree. It is guaranteed that $1 \le l \le r \le n$, and $x$ does not exceed the maximum node label currently present in any tree.
3. 2 x u v: This queries the distance between node $u$ and node $v$ in tree $x$, which is the number of edges on the shortest path between node $u$ and node $v$ in tree $x$. It is guaranteed that $1 \le x \le n$, and that nodes $u$ and $v$ exist in this tree.

Output

Output the answers to each of Little Y's queries in order, each on a new line.

Examples

Input 1

5 5
0 1 5
1 2 4 2
0 1 4
2 1 1 3
2 2 1 3

Output 1

1
2

Input 2

See forest/forest.in in the contestant directory.

Output 2

See forest/forest.ans in the contestant directory.

Constraints