Migrated from Lutece 2944 How Many Fruits

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在Q国的一座城堡的南侧分布着一排围墙，围墙内侧由一排果树组成。为了方便果树的打理，我们将果树从左到右依次标号为 $1...n$ 。

到了果子快要成熟的季节，Q国城堡里的管家将会特意为其额外施肥，但是由于城堡里的人力有限，每一次施肥并不一定能照顾到每一棵树，而只能照顾到其中编号为 $l ... r$ 中的树。每一次施肥会使得被施肥的树增加 $c$ 的果实数量。

但是Q国的天气并不稳定。这里的天气一共有两种，我们可以简单的理解为好天气与坏天气。在好天气的日子里，果树结果量不变，在坏天气的日子里，果树的结果量将会剧减。Q国的统计学家在统计分析后发现，每一次坏天气会使得果树的产量由原来的 $a_i$ 变为 $\lfloor log_2(a_i) \rfloor$ ，其中 $\lfloor . \rfloor$ 表示向下取整。特别的，当结果量已经为 $0$ 时，产量无法再减小。值得注意的是，Q国的城堡十分巨大，因此坏天气的影响是区域性的，我们可以将每一次坏天气的影响区域记录为一个 $l...r$ 的区间。

你作为Q国的特聘记录员之一，你的职责是估计Q国果树的最终产量。当然你不需要进行实地调查，管家会将每一次施肥记录报告给你，天气记录员也会将每天的天气情况报告给你。秉持着能摸尽摸的原则，你并不想对每一次报告都做复杂的运算，于是希望创造一个自动运行的记录程序，可以自动解析管家与天气记录员的给你的报告并进行运算。

同时，你还要应付上级的抽查，每一次抽查会询问你区间 $l ... r$ 区间内当前结果量预测，你需要报告每一次预测的结果。

Input

第一行，两个整数 $n, \ m$ 。$n$ 表示果树的数量， $m$ 表示管家、天气记录员的报告次数与预测结果的次数总和。

第二行，$n$ 个整数，$a_1,a_2,...,a_n$ 分别表示第 $i$ 棵果树的初始果实量。

接下来 $m$ 行，每行先输入三个个整数 $Type, \ l, \ r$ ，一共有三种可能：

• $Type = 1$ 表示 $[l,r]$ 区间遇到了一次坏天气。
• $Type = 2$ 表示 $[l,r]$ 区间进行了一次施肥，此时额外输入整数 $x$ ，表示该区间每棵果树增加 $x$ 的果实。
• $Type = 3$ 表示上级向你询问 $[l,r]$ 区间内的结果量。

Output

针对每一次询问，输出一行一个整数，表示询问的结果。

Samples

8 9
7 6 10 2 0 1 5 6
3 1 3
1 7 7
1 1 8
3 5 7
2 1 4 4
2 3 8 0
3 1 5
1 5 5
3 3 5

23
1
24
12

Constraints

$1\leq n, \ m \leq 3 \times10^5$, $0\leq a_i \leq 10^9$ , $Type \in \{1,2,3\}$ , $1\leq l \leq r \leq n$ , $0 \leq x \leq 10^6$

Resources

2023 UESTC ICPC Training for Data Structures