시간을 달리는 비타로

비버랜드에는 $N$개의 도시가 있고, 1번부터 $N$번까지 번호가 붙어 있다. $i$번째 ($1 \le i \le N-1$) 도로는 $i$번 도시와 $i+1$번 도시를 양방향으로 잇는다. 비버랜드의 하루는 1 000 000 000개의 단위시간으로 나뉘어 있으며, 이 단위시간을 쵸라고 부른다. 하루가 시작하고 $x$쵸가 지난 시점을 시각 $x$라고 한다. 도로 하나를 건너는 데에는 1쵸가 걸린다. $i$번째 도로는 시각 $L_i$부터 시각 $R_i$ 사이에만 건널 수 있다. 정확히는, $L_i \le x \le R_i - 1$을 만족하는 시각 $x$에 $i$번 도시 또는 $i+1$번 도시를 떠나, 시각 $x+1$에 다른 도시에 도착해야 한다.

비타로는 비버랜드에 사는 평범한 비버다. 지각을 자주 한 비타로는 이를 고치려고 애쓰다가 시간을 거슬러 올라갈 수 있는 능력을 얻었다. 이 능력을 한 번 쓰면 1쵸 뒤로 간다. 다만 어제로는 갈 수 없다. 시각 0과 시각 1 사이에 능력을 쓰면 시각 0으로 돌아간다. 이 능력은 도시에 있을 때만 쓸 수 있다. 능력을 써도 비타로의 위치는 변하지 않는다.

능력을 쓰면 비타로는 피곤해진다. 능력을 가장 적게 쓰는 이동 방법을 찾으려고 비타로는 $Q$번의 사고실험을 했다. 사고실험의 $j$번째 단계에서는 다음 중 하나를 한다.

• $P_j$번째 도로를 건널 수 있는 시각을 바꾼다. 바꾼 뒤에는 시각 $S_j$부터 시각 $E_j$ 사이에만 $P_j$번째 도로를 건널 수 있다.
• 시각 $B_j$에 $A_j$번 도시에 있을 때, 시각 $D_j$에 $C_j$번 도시로 이동하는 데 필요한 능력 사용 횟수의 최솟값을 구한다.

첫 줄에 $N$과 $Q$가 주어진다. 이어지는 $N-1$개의 줄에는 각각 $L_i$와 $R_i$가 주어진다. 그 다음 $Q$개의 질의가 한 줄에 하나씩 주어진다. 질의는 두 형식 중 하나이다.

• $T_j = 1$이면 $T_j$, $P_j$, $S_j$, $E_j$ 네 개의 정수가 주어진다.
• $T_j = 2$이면 $T_j$, $A_j$, $B_j$, $C_j$, $D_j$ 다섯 개의 정수가 주어진다.

$T_j = 2$인 각 질의마다 필요한 능력 사용 횟수의 최솟값을 질의 순서대로 한 줄에 하나씩 출력한다.

• $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$).