P14348 [JOISC 2019] 穿越时空 Bitaro / Bitaro, who Leaps through Time

Beaverland 由 $N$ 座城市组成，编号从 $1$ 到 $N$。共有 $N-1$ 条道路连接这些城市。第 $i$ 条道路（$1 \le i \le N-1$）双向连接城市 $i$ 和城市 $i+1$。在 Beaverland，他们使用 Byou 作为时间单位。Beaverland 中的每一天长度为 $1000000000$ Byous。每天从时刻 $0$ 开始，到时刻 $x$（$0 \le x < 1000000000$）称为时间 $x$。通过任意一条道路需要 $1$ Byou，且第 $i$ 条道路每天仅能在时间 $L_i$ 到 $R_i$ 之间通行。具体而言，要通过第 $i$ 条道路，必须在时间 $x$（满足 $L_i \le x \le R_i - 1$）从城市 $i$ 或城市 $i+1$ 出发，并在时间 $x+1$ 到达另一座城市。 Bitaro 曾是 Beaverland 中一名普通的海狸。然而，为了应对他的迟到问题，他最终习得了“穿越时间”的技能。使用该技能一次，他可以回到 1 Byou 之前的时间。但他无法回到当天之前：如果他在时间 $0$ 到 $1$ 之间使用该技能，他将回到当天的时间 $0$。他只能在位于某座城市时使用该技能。使用该技能不会改变 Bitaro 的位置。 Bitaro 在使用该技能时会感到疲惫。为了寻找使用该技能次数更少的旅行方式，他决定进行一个包含 $Q$ 步的思维实验。在思维实验的第 $j$ 步（$1 \le j \le Q$），他执行以下操作之一： - 修改第 $P_j$ 条道路的可通行时间段。修改后，该道路仅能在时间 $S_j$ 到 $E_j$ 之间通行。 - 假设他在时间 $B_j$ 位于城市 $A_j$，计算到达城市 $C_j$ 且时间为 $D_j$ 的当天所需的最少技能使用次数。 他想知道该思维实验的结果。 请编写一个程序，输入 Beaverland 的城市数量、道路信息以及思维实验的细节，计算并输出该思维实验的结果。

从标准输入读取以下数据。输入中的所有值均为整数。 $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$ 步中，你的程序应在假设 Bitaro 在时间 $B_j$ 位于城市 $A_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 到达城市 2。然后，他使用技能四次，用 1 Byou 移动到城市 3，并等待 2 Byous，从而在时间 3 到达城市 3。 ### 数据范围 - $1 \le N \le 300000$。 - $1 \le Q \le 300000$。 - $0 \le L_i < R_i \le 999999999$（$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 \le 999999999$（$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 \le 999999999$（$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 \le 999999999$（$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 分）无额外约束。