在一个高科技工业设施中，一系列核反应堆排成一列。每个反应堆都在严格的气压规定下运行，以确保安全和效率。为了防止严重故障，每个反应堆都有一个特定的最大气压限制。当反应堆的内部气压达到或超过该限制时，就会启动受控的气压释放（排气）。由于动态的运行调整和持续监控的需求，该系统需要精细的管理。

你需要设计并实现一个系统来管理一排 $n$ 个反应堆的气压。反应堆的编号为 $1$ 到 $n$，每个反应堆的初始最大气压限制为 $p_i$。所有反应堆的初始气压均为 $0$。系统必须支持以下两种操作：

1. 气压增加操作：对于给定的反应堆区间 $[l, r]$，将其气压增加 $k$ 个单位。如果该区间内任何反应堆的气压达到或超过其最大限制，它将进行排气，并将其气压重置为 $0$。同时，排气反应堆的最大气压限制将更新为 $\max(\lfloor \frac{p_{old}}{2} \rfloor, 1)$，其中 $p_{old}$ 是当前气压增加操作之前该反应堆的最大气压限制。
2. 排气次数查询：对于给定的反应堆区间 $[l, r]$，你需要报告自系统开始运行以来，该指定区间内所有反应堆发生的排气操作总次数。

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示反应堆的数量和操作的数量。

第二行包含 $n$ 个整数，第 $i$ 个整数 $p_i$ 表示第 $i$ 个反应堆的初始最大气压限制。

接下来的 $q$ 行描述了这些操作。每行以一个整数 $op$ 开始。

• 如果 $op = 1$，后面跟着三个整数 $l$、$r$ 和 $k$，表示对区间 $[l, r]$（闭区间）内的反应堆进行气压增加操作，增加 $k$ 个单位。
• 如果 $op = 2$，后面跟着两个整数 $l$ 和 $r$，表示对区间 $[l, r]$（闭区间）内的反应堆进行排气次数查询。

输出格式

对于每个 $op = 2$ 的查询，在新的一行中输出一个整数，表示自系统开始运行以来，指定区间内所有反应堆发生的排气操作总次数。

数据范围

• $1 \le n \le 2 \times 10^5$
• $1 \le q \le 2 \times 10^5$
• $1 \le p_i \le 4 \times 10^5$
• $1 \le l \le r \le n$
• $1 \le k \le 4 \times 10^5$
• 保证至少存在一次排气次数查询。

样例

输入样例 1

10 5
5 10 23 45 10 45 65 10 68 9
1 5 10 664
1 2 9 5
2 4 10
1 8 8 5
2 1 10

输出样例 1

8
9

输入样例 2

10 10
79 26 9 28 13 40 26 54 69 19
1 1 5 6
1 5 7 2
2 4 7
1 9 10 19
2 5 7
1 5 7 27
2 10 10
2 9 9
1 6 6 20
1 3 8 6

输出样例 2

0
0
1
0

输入样例 3

10 10
56 29 49 42 47 21 23 54 8 31
2 9 9
1 5 6 23
2 6 7
2 4 7
1 5 6 68
2 1 9
2 3 6
1 2 10 89
2 6 8
1 3 6 53

输出样例 3

0
1
1
3
3
5