AT_joisc2019_i Bitaro, who Leaps through Time

Beaverland consists of $N$ cities, numbered from $1$ to $N$. There are $N − 1$ roads connecting cities. The $i$-th ($1\le i\le N−1$) road connects the city $i$ and the city $i+1$ bidirectionally. In Beaverland, they use Byou as the unit of time. Each day in Beaverland is $10^9$ Byous long. The moment $x$ Byous ($0 ≤ x < 10^9$) after the beginning of a day is called time $x$. It takes $1$ Byou to pass through any of the roads, and the $i$-th road can be passed through only between time $L_i$ and time $R_i$ every day. Specifically, to pass through the $i$-th road, we must leave the city $i$ or the city $i + 1$ at time $x$ satisfying $L_i\le x\le R_i − 1$, and must arrive at the other city at time $x + 1$. Bitaro used to be an ordinary Beaver living in Beaverland. However, as he tries to cope with his lateness, he has finally acquired the skill of leaping through time. By using this skill once, he can go back $1$ Byou ago. He cannot go back to the day before: if he uses the skill between time $0$ and time $1$, he will go back to time $0$ of the day. He can use this skill only when he is at a city. The position of Bitaro does not change on using the skill. Bitaro gets tired when he uses the skill. To find ways to travel with fewer number of usage of the skill, he decided to do a thought experiment consisting of $Q$ steps. In the $j$-th ($1\le j\le Q)$ step in the thought experiment, he does one of the followings: - Change the duration in which the $P_j$-th road can be traveled. After the modification, it can be passed through only between time $S_j$ and time $E_j$. - Suppose he is at the city $A_j$ at time $B_j$. Then, compute the minimum number of usage of the skill to be at the city $C_j$ at time $D_j$ on the day. He wonders the result of the thought experiment. Write a program which, given the number of cities in Beaverland, the information of roads, and the details of the thought experiment, calculates the result of the thought experiment.

Read the following data from the standard input. All the values in the input are integers. $N\ Q$ $L_1\ R_1$ $\vdots$ $L_{N−1}\ R_{N−1}$ $(Query 1)$ $\vdots$ $(Query Q)$ Here, each (Query $j$) consists of $4$ or $5$ integers separated by a space. Let $T_j$ be the first integer in it. Then, - If $T_j = 1$, (Query $j$) consists of $4$ integers $T_j, P_j, S_j$ and $E_j$. This means that, in the $j$-th step of the thought experiment, the duration in which the $P_j$-th road can be passed is changed to the interval between time $S_j$ and time $E_j$. - If $T_j = 2$, (Query $j$) consists of $5$ integers $T_j, A_j, B_j, C_j$ and $D_j$. This means that, in the $j$-th step of the thought experiment, your program should compute the minimum number of usage of the skill to be at the city $C_j$ at time $D_j$ on the day, on the assumption that Bitaro is at the city $A_j$ at time $B_j$.

For each step with $T_j = 2$, write a line containing the minimum number of usage of the skill to the standard output, in order.

**【样例解释 #1】** In the $1$st step of the thought experiment, Bitaro moves from the city $1$ to the city $2$ in $1$ Byou, then moves from the city $2$ to the city $3$ in $1$ Byou to be at the city $3$ at time $5$. Therefore, by using the skill twice, he can be at the city $3$ at time $3$. In the $2$nd step of the thought experiment, the duration in which the $2$nd road can be passed is changed to the interval between time $0$ and time $1$. In the $3$rd step of the thought experiment, Bitaro moves from the city $1$ to the city $2$ in $1$ Byou to be at the city $2$ at time $4$. Then, he uses the skill four times, moves to the city $3$ in $1$ Byou and wait $2$ Byous to be at the city $3$ at time $3$. **【数据范围】** - $1\le N\le 300 000$. - $1\le Q\le 300 000$. - $0\le L_i < R_i < 10^9 (1\le i\le N − 1)$. - $1\le T_j\le 2 (1\le j\le Q)$. - $1\le P_j\le N − 1 (1\le j\le Q，T_j = 1)$. - $0\le S_j < E_j < 10^9 (1\le j\le Q，T_j = 1)$. - $1\le A_j\le N (1\le j\le Q，T_j = 2)$. - $0\le B_j < 10^9 (1\le j\le Q，T_j = 2)$. - $1\le C_j\le N (1\le j\le Q，T_j = 2)$. - $0\le D_j < 10^9 (1\le j\le Q，T_j = 2)$. 1. ($4$ points) $N\le 1000, Q\le 1000$. 2. ($30$ points) $T_j = 2 (1\le j\le Q)$. 3. ($66$ points) No additional constraints.