Beaverland 由 $N$ 座城市组成，编号为 $1$ 到 $N$。城市之间有 $N-1$ 条道路。第 $i$ 条道路（$1 \le i \le N-1$）双向连接城市 $i$ 和城市 $i+1$。在 Beaverland，时间单位为 Byou。每天的长度为 $1\,000\,000\,000$ Byou。一天开始后 $x$ Byou 的时刻（$0 \le x < 1\,000\,000\,000$）被称为时刻 $x$。通过任何一条道路需要 $1$ Byou，且第 $i$ 条道路每天仅能在时刻 $L_i$ 到时刻 $R_i$ 之间通过。具体来说，要通过第 $i$ 条道路，必须在满足 $L_i \le x \le R_i - 1$ 的时刻 $x$ 从城市 $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$ 之间通过。
• 假设他处于城市 $A_j$，时刻为 $B_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 处于城市 $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$)
• $0 \le S_j < 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$)
• $0 \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$)
• $0 \le D_j \le 999\,999\,999$ ($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 分) 无附加限制

样例

输入格式 1

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

输出格式 1

2
4

说明

在第 1 步思想实验中，Bitaro 在 1 Byou 内从城市 1 移动到城市 2，然后在 1 Byou 内从城市 2 移动到城市 3，于时刻 5 到达城市 3。因此，通过使用两次技能，他可以在时刻 3 到达城市 3。

在第 2 步思想实验中，第 2 条道路的可通行时间段被修改为时刻 0 到时刻 1。

在第 3 步思想实验中，Bitaro 在 1 Byou 内从城市 1 移动到城市 2，于时刻 4 到达城市 2。然后，他使用四次技能，在 1 Byou 内移动到城市 3，并等待 2 Byou，于时刻 3 到达城市 3。

输入格式 2

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

输出格式 2

4
3
2
3

输入格式 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

输出格式 3

145611455
0
447180143
0
207252171
0
0

输入格式 4

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

输出格式 4

10467449
164858601