当前没有测试数据。

搞科研

题目背景

每日科研（bushi

题目描述

小S是某实验室的研究人员，他正在研究一条食物链。食物链中的每个物种数量不同。小S表示，如果一个物种的数量太多的话，研究经费将会爆炸。所以他在搞科研的时候，会进行两种操作：

1. 【操作一】将某一给定区间 $[l, r]$ 内的每一个物种都增加 $k$。
2. 【操作二】查询某一给定区间 $[l, r]$ 内每一个物种数量的和，并找到其中最大的物种数量。此时，如果这个物种数量最多的物种数量如果超过了区间内所有物种数量的一半，就将该物种数量减少一半（向下取整）

输入格式

第一行包含两个整数 $n, m$，分别表示该食物链中各个物种的数量和操作总次数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示食物链中第 $i$ 个物种的初始数量。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

1. 1 x y k：对应题目描述【操作一】。
2. 2 x y：对应题目描述【操作二】。

输出格式

输出包含若干行整数，即为所有【操作二】的结果。

样例 #1

样例输入 #1

样例暂时木的有

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

样例输出 #1

样例暂时木的有

11
8
20

提示

对于 $30\%$ 的数据：$n \le 8$，$m \le 10$。
对于 $70\%$ 的数据：$n \le {10}^3$，$m \le {10}^4$。
对于 $100\%$ 的数据：$1 \le n, m \le {10}^5$。

保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$。