Time-Traveling Vitaro

Beverland has $N$ cities numbered 1 through $N$. The $i$-th road ($1 \le i \le N-1$) connects city $i$ and city $i+1$ in both directions. A day in Beverland is divided into 1 000 000 000 unit times, called cho. The moment $x$ cho after the start of a day is called time $x$. Crossing a road takes 1 cho. The $i$-th road can be crossed only between time $L_i$ and time $R_i$. To be exact, to cross the $i$-th road, one must leave city $i$ or city $i+1$ at a time $x$ with $L_i \le x \le R_i - 1$ and arrive at the other city at time $x+1$.

Vitaro is an ordinary beaver who lives in Beverland. He was often late, and while trying to fix that, he gained the ability to go back in time. Each use of the ability sends him back 1 cho. He cannot go back to yesterday. If he uses the ability between time 0 and time 1, he returns to time 0. He can use this ability only while he is in a city. His position does not change when he uses the ability.

Using the ability makes Vitaro tired. To find a way to move with the fewest uses of the ability, Vitaro ran $Q$ thought experiments. In step $j$ of the experiments, he does one of the following:

• Changes the times at which the $P_j$-th road can be crossed. After the change, the $P_j$-th road can be crossed only between time $S_j$ and time $E_j$.
• Starts in city $A_j$ at time $B_j$ and finds the minimum number of uses of the ability needed to reach city $C_j$ at time $D_j$.

The first line contains $N$ and $Q$. Each of the next $N-1$ lines contains $L_i$ and $R_i$. Then $Q$ queries follow, one per line. Each query has one of two forms.

• If $T_j = 1$, the query consists of four integers $T_j$, $P_j$, $S_j$, $E_j$.
• If $T_j = 2$, the query consists of five integers $T_j$, $A_j$, $B_j$, $C_j$, $D_j$.

For each query with $T_j = 2$, print the minimum number of uses of the ability, one per line, in the order the queries appear.

• $1 \le N \le 300\ 000$.
• $1 \le Q \le 300\ 000$.
• $0 \le L_i < R_i \le 999\ 999\ 999$ ($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$).
• $1 \le S_j \le E_j \le 999\ 999\ 999$ ($1 \le j \le Q$, $T_j = 1$).
• $1 \le A_j \le N$ ($1 \le j \le Q$, $T_j = 2$).
• $1 \le B_j \le 999\ 999\ 999$ ($1 \le j \le Q$, $T_j = 2$).
• $1 \le C_j \le N$ ($1 \le j \le Q$, $T_j = 2$).
• $1 \le D_j \le 999\ 999\ 999$ ($1 \le j \le Q$, $T_j = 2$).