시간을 달리는 비타로

비버랜드에는 $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$ 사이에만 통과할 수 있다. 구체적으로, $i$번째 도로를 통과하기 위해서 우리는 도시 $i$나 $i+1$을 $L\_i \le x \le R\_i -1$ 을 만족하는 시각 $x$에 떠나야 하고, 다른 도시에 시각 $x+1$에 도착해야 한다.

비타로는 비버랜드에 사는 평범한 비버다. 아니, 비버였다 라고 하는게 옳은 것일까. 지각을 자주한 비타로는 이를 개선하려고 한 결과로 시간을 거슬러 올라가는게 가능해 졌다. 이 능력을 한 번 사용하면 1쵸 뒤로 갈 수 있다. 하지만, 어제로 갈 수는 없다. 만약 그가 능력을 시각 0과 시각 1 사이에 사용했다면, 그는 시각 0으로 돌아갈 것이다. 그는 이 기술을 도시에 있을 때 사용할 수 있다. 비타로의 위치는 능력을 사용해도 변하지 않는다.

비타로는 기술을 사용하면 피곤해 진다. 최소한의 기술을 사용하여 이동하는 방법을 찾기 위한 비타로는 $Q$개의 사고실험을 진행했다. 사고 실험의 $j$ 번째 단계에서는, 그는 다음 중 한 행동을 한다:

• $P\_j$ 번째 도로가 여행될수 있는 시각을 바꾼다. 바뀐 이후에는, 시각 $S\_j$와 시각 $E\_j$ 사이에만 $P\_j$ 번째 도로를 통과할 수 있다.
• 그가 $A\_j$번 도시, 시각 $B\_j$에 있다고 할 때, $C\_j$번 도시, 시각 $D\_j$로 이동하기 위해 사용해야하는 능력의 수의 최솟값을 구하여라.

그는 사고실험의 결과를 궁금해한다.

비버랜드의 도시의 수, 도로의 정보, 사고실험의 방법이 주어졌을 때, 사고 실험의 결과를 계산하는 프로그램을 작성하여라.

표준 입력에서 다음과 같은 형식으로 주어진다. 모든 값은 정수이다.

$N$ $Q$

$L\_1$ $R\_1$

$\vdots$

$L\_{N-1}$ $R\_{N-1}$

(Query 1)

$\vdots$

(Query $Q$)

여기서, (Query $j$)는 공백으로 구분된 4개나 5개의 정수로 이루어져 있다. $T\_j$가 첫 번째 정수라고 하자. 그러면,

• $T\_j=1$인 경우, (Query $j$)는 4개의 정수 $T\_j$, $P\_j$, $S\_j$, $E\_j$로 이루어져 있다. 이것은, 사고 실험의 $j$번째 단계에서, $P\_j$번째 도로를 지날수 있는 시간이 시각 $S\_j$와 시각 $E\_j$ 사이로 바뀐다는 것을 의미한다.
• $T\_j=2$인 경우, (Query $j$)는 5개의 정수 $T\_j$, $A\_j$, $B\_j$, $C\_j$, $D\_j$로 이루어져 있다. 이는, $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$ ($q \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$).