题目描述

给定长度为 $n$ 的正整数序列 $a$。对于正整数 $x$，定义 $\operatorname{lowbit}(x)$ 为 $x$ 的二进制表示中最低位的 $1$ 所代表的数值。例如，$12$ 的二进制表示为 $1100$，所以 $\operatorname{lowbit}(12)=4$。

依次执行 $q$ 次操作。每次操作给出类型 $t$ 和下标区间 $[l,r]$：

• $t=1$：将区间内每个 $a_i$ 改为 $a_i+\operatorname{lowbit}(a_i)$；
• $t=2$：将区间内每个 $a_i$ 加 $1$；
• $t=3$：输出区间内所有数的和。

每次修改立即生效，后续操作使用修改后的序列。保证初始以及每次操作后均有 $1\le a_i<2^{50}$。

输入格式

第一行包含两个整数 $n,q$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行包含三个整数 $t,l,r$。

输出格式

对每个类型为 $3$ 的操作，输出一行一个整数，表示当前区间和。

样例

输入

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

输出

14
20
21

样例解释

初始总和为 $14$。两次修改后，序列依次变为 $(2,4,8,6)$、$(2,5,9,7)$，后两次查询的答案分别为 $20,21$。

数据范围

对于所有测试点，$1\le n\le5\times10^5$，$1\le q\le3\times10^5$，$1\le t\le3$，$1\le l\le r\le n$，初始及每次操作后均有 $1\le a_i<2^{50}$。所有输入数均为整数。

特殊性质 A：每个类型为 $1$ 或 $2$ 的操作均满足 $l=r$。

特殊性质 B：不存在类型为 $1$ 的操作。

特殊性质 C：不存在类型为 $2$ 的操作。

特殊性质 D：每个类型为 $1$ 或 $2$ 的操作均满足 $l=1,r=n$。