AT_joisc2019_i.Bitaro, who Leaps through Time

比弗兰由 $N$ 个城市组成，编号为 $1$ 到 $N$。这些城市之间有 $N-1$ 条道路连接。第 $i$ 条道路（$1 \le i \le N-1$）双向连接城市 $i$ 和城市 $i+1$。在比弗兰，时间单位称为 Byou。每一天有 $10^9$ Byou。一天开始后的第 $x$ Byou 时刻（$0 \le x < 10^9$）被称为时间 $x$。通过任意一条道路都需要 $1$ Byou，而第 $i$ 条道路每天只能在时间 $L_i$ 到时间 $R_i$ 之间通过。具体来说，要通过第 $i$ 条道路，必须在时间 $x$ 离开城市 $i$ 或城市 $i+1$（满足 $L_i \le x \le R_i-1$），并在时间 $x+1$ 抵达另一个城市。

Bitaro 曾是比弗兰的普通居民，但由于常常迟到，他终于获得了穿越时间的能力。每使用一次该技能，可以回到 $1$ Byou 之前。他不能回到前一天：如果在时间 $0$ 到 $1$ 之间使用该技能，只会回到本日的时间 $0$。他只能在城市中使用该技能，使用时位置不会改变。

使用技能会让 Bitaro 感到疲惫。为了找到更少使用技能的旅行方法，他决定进行一系列共 $Q$ 步的推演实验。在第 $j$ 步实验（$1 \le j \le Q$）中，他将进行以下操作之一：

• 修改第 $P_j$ 条道路可以通行的时间区间。修改后，第 $P_j$ 条道路只能在 $S_j$ 到 $E_j$ 之间通过。

• 假如他在一天中的时间 $B_j$ 处于城市 $A_j$，计算他在当天时间 $D_j$ 到达城市 $C_j$ 时，最少需要用多少次技能。

他想知道全部推演实验的结果。

请编写程序，给出比弗兰的城市数量、道路信息和推演实验内容，计算推演实验的结果。

从标准输入读取以下数据。输入中的所有值均为整数。

$N\ Q$
$L_1\ R_1$
$\vdots$
$L_{N-1}\ R_{N-1}$
（第 1 条查询）
$\vdots$
（第 $Q$ 条查询）

其中每条查询由以空格分隔的 $4$ 或 $5$ 个整数组成。令 $T_j$ 表示其第一个整数，则

• 若 $T_j = 1$，该查询由 $4$ 个整数 $T_j, P_j, S_j, E_j$ 组成，表示在第 $j$ 步将第 $P_j$ 条路可通过时间区间改为 $S_j$ 到 $E_j$。

• 若 $T_j = 2$，该查询由 $5$ 个整数 $T_j, A_j, B_j, C_j, D_j$ 组成，表示在第 $j$ 步假设当前处于城市 $A_j$、时间 $B_j$，要求在当天时间 $D_j$ 到达城市 $C_j$ 最少需要使用技能的次数。

对于每一次 $T_j = 2$ 类型的查询，输出一行答案，依次表示最少使用技能次数。

【样例解释 #1】

在第 1 步推演实验中，Bitaro 从城市 $1$ 用 $1$ Byou 移动到城市 $2$，然后再用 $1$ Byou 从城市 $2$ 移动到城市 $3$，最终在时间 $5$ 抵达城市 $3$。因此，如果要在时间 $3$ 抵达 $3$ 号城市，需要在到达后使用技能两次。

在第 2 步实验中，第 2 条道路的可通过时间区间改为 $0$ 到 $1$。

在第 3 步实验中，Bitaro从城市 $1$ 用 $1$ Byou 到达城市 $2$（时间 $4$），再用技能 $4$ 次回溯到时间 $0$，再用 $1$ Byou移动到城市 $3$，等待 $2$ Byou 至时间 $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$ 分）$N\le 1000, Q\le 1000$。
2.（$30$ 分）所有 $T_j = 2 (1\le j\le Q)$。
3.（$66$ 分）无其他限制。

由 ChatGPT 5 翻译