你喜欢处理包含多种查询的数据结构问题吗？如果是的话，这里有一个：

给定一个包含 $2^p$ 个整数的数组 $a$。数组中的元素从零开始编号。你需要处理五种类型的查询：

1. add v δ：将数组中第 $v$ 个元素增加 $\delta$。
2. sum l r：计算区间 $[l, r]$ 内元素的和。
3. and k：该查询可以用以下伪代码描述：

   b = array of 2^p zeroes
   for i in 0..2^p - 1:
   b[i and k] += a[i]
   a = b

4. or k：该查询可以用以下伪代码描述：

   b = array of 2^p zeroes
   for i in 0..2^p - 1:
   b[i or k] += a[i]
   a = b

5. xor k：该查询可以用以下伪代码描述：

   b = array of 2^p zeroes
   for i in 0..2^p - 1:
   b[i xor k] += a[i]
   a = b

上述伪代码中的二进制运算 and、or 和 xor 分别表示整数的按位与、按位或和按位异或运算；$2^p$ 表示 $2$ 的 $p$ 次幂。

输入格式

第一行包含两个整数 $p$ 和 $q$ ($0 \le p \le 19, 1 \le q \le 5 \cdot 10^5$)，中间用单个空格隔开。 第二行包含 $2^p$ 个整数 $a_i$ ($1 \le a_i \le 10^9$)，中间用空格隔开：即数组的初始元素。 接下来的 $q$ 行，每行包含以下查询之一：

• add v δ ($0 \le v \le 2^p - 1, 1 \le \delta \le 10^9$)
• sum l r ($0 \le l \le r \le 2^p - 1$)
• and k ($0 \le k \le 2^p - 1$)
• or k ($0 \le k \le 2^p - 1$)
• xor k ($0 \le k \le 2^p - 1$)

输出格式

对于每个 sum 类型的查询，在单独的一行中输出一个整数：该查询的答案。

样例

输入 1

3 6
1 4 2 8 5 7 4 2
add 0 3
sum 3 5
and 5
sum 1 4
xor 7
sum 0 2

输出 1

20
21
9

说明

在第一次查询后，数组变为 $3, 4, 2, 8, 5, 7, 4, 2$。 在第三次查询后，数组变为 $5, 12, 0, 0, 9, 9, 0, 0$。 在第五次查询后，数组变为 $0, 0, 9, 9, 0, 0, 12, 5$。