题目描述

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$ 的步骤，按顺序在标准输出中输出一行，包含所需的最少技能使用次数。

3 3
0 5
0 5
2 1 3 3 3
1 2 0 1
2 1 3 3 3

2
4

5 5
3 5
4 8
2 6
5 10
2 5 3 1 10
2 2 6 5 6
1 3 4 6
2 3 3 4 3
2 4 5 1 5

4
3
2
3

7 7
112103440 659752416
86280800 902409187
104535475 965602300
198700180 945132880
137957976 501365807
257419446 565237610
2 4 646977260 7 915994878
2 1 221570340 6 606208433
2 7 948545948 4 604273995
2 7 247791098 5 944822313
2 7 250362511 2 50167280
2 3 364109400 4 555412865
2 7 33882587 7 186961394

145611455
0
447180143
0
207252171
0
0

7 7
535825574 705426142
964175291 996597835
481817391 649559926
4519006 410772613
74521477 274584126
256535565 899389890
1 6 511428966 602601933
1 1 69986642 201421232
2 3 636443425 4 625975977
1 6 235225515 405336399
2 3 866680458 3 701821857
1 6 180606048 900533151
1 6 612564160 720179605

10467449
164858601

提示

样例 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 分）无额外约束。