题目背景

lzy 给了 Cute_QiQi 很多组神奇的磁铁。

注：想拿到快速 AK 变换奖请在代码注释部分写明本题代码正确性证明。

题目描述

一组神奇的磁铁由 $2x$ 个磁铁排成一排组成，编号 $1,2,\dots,2x$，有激活和未激活两种状态。它们与普通的磁铁不同，不会简单地吸在一起。对于一组磁铁，当且仅当存在 $y \in [1,x]$，使得不存在两个激活的磁铁满足两者之间的距离为 $y$，整组磁铁才会吸在一起。不同组的磁铁之间不相互影响。

对于编号为 $i,j$ 的两个磁铁，它们之间的距离为 $|i-j|$。具体地，当 $x=2$ 时，磁铁组为 $\{1,2,3,4\}$。当激活的磁铁为 $\{1,2\}$ 时，整组磁铁可以吸在一起，因为对于 $y=2$，不存在两个磁铁之间的距离为 $2$。而激活的磁铁为 $\{1,2,3\}$ 时整组磁铁不能吸在一起。

lzy 给了 Cute_QiQi $n$ 组磁铁。现在，Cute_QiQi 希望把这 $n$ 组磁铁排成一排作为装饰，同组磁铁堆在一起。未被吸在一起的磁铁不便于摆放，因此，Cute_QiQi 希望所有的磁铁组内的磁铁都吸在一起。在此基础上，Cute_QiQi 希望激活尽可能多的磁铁。

另外，有时 lzy 会给 Cute_QiQi 一些额外的磁铁。

磁铁实在是太多了，以至于 Cute_QiQi 计算不出她最多能激活多少磁铁。因此，她希望你帮她写一个程序，支持下面两种操作：

• 1 l r x，表示 lzy 给 $[l,r]$ 内所有的磁铁组添加了 $2x$ 个磁铁；
• 2 l r，表示 Cute_QiQi 想知道在激活最多磁铁的情况下，$[l,r]$ 内的磁铁组总共有多少个磁铁被激活。

输入格式

输入第一行为 $n,q$，其中 $q$ 表示操作的个数。

第二行为 $n$ 个整数 $a_1,a_2,.\dots,a_n$，表示每个磁铁组中初始的磁铁数量 $2a_i$。

以下 $q$ 行，每行一个操作，格式如下：

• 1 l r x，表示 lzy 给 $[l,r]$ 内所有的磁铁组添加了 $2x$ 个磁铁；
• 2 l r，表示 Cute_QiQi 想知道在激活最多磁铁的情况下，$[l,r]$ 内的磁铁组总共有多少个磁铁被激活。

输出格式

对于每个 2 l r 操作，输出一行表示答案。

6 6
1 1 4 5 1 4
2 1 6
1 1 3 2
2 1 4
2 1 6
1 1 3 -2
2 1 6

19
22
28
19

提示

样例解释

初始时对应的激活磁铁的最大数量依次为 $1,1,5,6,1,5$。

进行修改操作后，对应的激活磁铁最大数量依次为 $4,4,8,6,1,5$。

可以证明，不可能再激活更多的磁铁。

数据规模与约定

本题采用捆绑测试。

设 $v$ 表示任意时刻，磁铁数最多的磁铁组内磁铁的数量。

对于所有数据，保证 $1 \le n,q \le 5 \times 10^5, 1 \le l \le r \le n, 1 \le v,a_i \le 10^9, -10^9 \le x \le 10^9$。