Damian 正在制作一款电子游戏！游戏包含 $N$ 个关卡，第 $i$ 个关卡初始时的难度为 $D_i$。得益于最先进的游戏设计，该游戏既可以正着玩，也可以倒着玩。当然，让玩家感受到“进步感”也很重要——难度应该以恒定的速率变化。因此，Damian 会进行一系列操作。

他会进行两种类型的操作。第一种操作是修改（patch）操作，由四个整数 $L, R, S$ 和 $C$ 定义，表示对于所有满足 $L \le i \le R$ 的关卡 $i$，其难度 $D_i$ 将增加 $S + (i - L) \times C$。

第二种操作是重写（rewrite）操作，由四个整数 $L, R, S$ 和 $C$ 定义，表示对于所有满足 $L \le i \le R$ 的关卡 $i$，其难度 $D_i$ 将被设置为 $S + (i - L) \times C$。

Damian 认为，一个连续的关卡子序列构成一个可玩区间，当且仅当它们的难度以恒定的速率变化（毕竟，玩家总是可以倒着玩游戏）！换句话说，关卡 $a$ 到 $b$（其中 $1 \le a \le b \le N$）构成一个可玩区间，当且仅当对于所有 $a \le i < b$，都有 $D_{i+1} - D_i = k$，其中 $k$ 是某个整数（可能满足 $k \le 0$）。单个关卡本身构成一个长度为 $1$ 的可玩区间。

有时，Damian 会进行一次评估（evaluate）查询，由两个整数 $L$ 和 $R$ 定义，表示他希望找到此时介于关卡 $L$ 和 $R$ 之间（即完全包含在区间 $[L, R]$ 内）的最长可玩区间的长度。

遗憾的是，Damian 的操作并不一定会改善游戏体验。因此，他需要你的帮助来回答这些查询，以便他能够开发出最好的游戏。

输入格式

你的程序必须从标准输入中读取。

第一行包含两个整数 $N$ 和 $Q$，分别表示关卡数量以及操作和查询的总数。

第二行包含 $N$ 个空格分隔的整数 $D_1, \dots, D_N$，如上所述。

接下来的 $Q$ 行，每行代表一个操作或查询。

• 如果该行以整数 $1$ 开头，则接下来的 $4$ 个整数为 $L, R, S$ 和 $C$，代表一次修改操作。
• 如果该行以整数 $2$ 开头，则接下来的 $4$ 个整数为 $L, R, S$ 和 $C$，代表一次重写操作。
• 如果该行以整数 $3$ 开头，则接下来的 $2$ 个整数为 $L$ 和 $R$，代表一次评估查询。

输出格式

你的程序必须输出到标准输出。

对于每次评估查询，输出一行，包含一个整数，表示此时介于关卡 $L$ 和 $R$ 之间的最长可玩区间的长度。

实现细节

由于子任务 1、3、4、5 和 6 的输入数据量可能非常大，建议你使用带有快速输入输出的 C++ 来解决此问题。科学委员会没有能够完全解决此问题的 Python 解决方案。

附件中提供了包含快速输入/输出模板的 C++ 和 Java 源文件。强烈建议你使用这些模板。

如果你使用 Java 实现解决方案，请将文件命名为 Progression.java，并将主函数放在 Progression 类中。

数据范围

最大执行时间为 3.0 秒，最大内存使用量为 1 GiB。对于所有测试用例，输入将满足以下范围：

• $1 \le N, Q \le 3 \times 10^5$
• $-10^6 \le D_i, S, C \le 10^6$
• $1 \le L \le R \le N$

在给定的限制下，保证 $D_i$ 在任何时候都适合 64 位有符号整数。

子任务

你的程序将在满足以下限制的输入实例上进行测试：

样例

输入 1

10 6
1 2 3 4 1 2 3 4 5 5
3 1 10
1 1 4 -1 -1
3 1 10
3 9 10
2 5 10 -2 -2
3 1 10

输出 1

5
6
2
7

说明 1

对于第一次评估查询，关卡 5 到 9 构成了最长的可玩区间（此时 $k = 1$）。

在修改操作之后，难度变为 $[0, 0, 0, 0, 1, 2, 3, 4, 5, 5]$。

对于第二次评估查询，关卡 4 到 9 构成了最长的可玩区间（此时 $k = 1$）。

对于第三次评估查询，关卡 9 到 10 构成了最长的可玩区间（此时 $k = 0$），因为我们只考虑介于关卡 $L = 9$ 和 $R = 10$ 之间的关卡。

在重写操作之后，难度变为 $[0, 0, 0, 0, -2, -4, -6, -8, -10, -12]$。

对于最后一次评估查询，关卡 4 到 10 构成了最长的可玩区间（此时 $k = -2$）。

输入 2

10 5
1 2 3 4 1 2 3 4 5 5
3 1 10
1 1 10 1 2
3 1 10
2 1 10 3 4
3 1 10

输出 2

5
5
10

输入 3

10 5
1 2 3 4 1 2 3 4 5 5
3 1 4
3 4 5
3 2 4
3 5 9
3 10 10

输出 3

4
2
3
5
1

输入 4

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

输出 4

6
5
5

说明 4

请注意，当 $L = R$ 时，$C$ 不一定为 $0$。然而，它的值与该操作无关。

输入 5

10 5
1 2 3 4 1 2 3 4 5 5
1 1 4 -1 -1
3 1 5
3 4 5
1 5 10 -1 -1
3 1 10

输出 5

4
2
9