Description

Xiao Y has a great forest at home, containing $n$ trees numbered from $1$ to $n$. Initially, each tree is just a sapling with a single node labeled $1$. Each tree has a special node, called the growth node, which can grow a child node.

Xiao Y masters a kind of magic that can make the growth nodes of the $l$-th tree to the $r$-th tree each grow one child node. She can also modify the growth nodes of the $l$-th tree to the $r$-th tree. She told you the log of her magic operations. Can you manage her forest and answer her queries?

Input Format

The first line contains $2$ positive integers $n, m$, meaning there are $n$ trees and $m$ operations.

Then follow $m$ lines. Each line contains several non-negative integers describing one operation, in one of the following formats:

0 l r Make each growth node of the $l$-th tree to the $r$-th tree grow one child. The label of the new child equals the label generated by the previous operation of type 0 plus $1$ (for example, the first operation of type 0 generates a child with label $2$). The trees from $l$ to $r$ all get a child with the same label. It is guaranteed that $1 \leq l \leq r \leq n$.

1 l r x Set the growth node of each tree from the $l$-th to the $r$-th to the node labeled $x$. For the $i$-th tree ($l \leq i \leq r$), if the node labeled $x$ is not in that tree, this operation has no effect on that tree. It is guaranteed that $1 \leq l \leq r \leq n$, and $x$ does not exceed the current maximum label among all trees.

2 x u v Query the distance between node $u$ and node $v$ in the $x$-th tree, i.e., the number of edges on the shortest path between $u$ and $v$ in the $x$-th tree. It is guaranteed that $1 \leq x \leq n$, and nodes $u$ and $v$ exist in this tree.

Output Format

Output several lines. For each of Xiao Y’s queries, print the answer in order.

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

1
2

Hint

For $100\%$ of the testdata, $N \leq 10^5, M \leq 2 \times 10^5$.

Translated by ChatGPT 5