시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 512 MB 7 4 3 50.000%

## 문제

Do you like data structure problems with many types of queries? If so, here is one of them:

You are given an array a of 2p integers. The items in the array are numbered starting from zero. You have to process five types of queries:

1. add v δ: increase the v-th element of the array by δ.

2. sum l r: compute the sum of the items on the segment [l, r].

3. and k: this query can be described by the following pseudocode:

b = array of 2^p zeroes
for i in 0..2^p - 1:
b[i and k] += a[i]
a = b
4. or k: this query can be described by the following pseudocode:

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

5. xor k: this query can be described by the following pseudocode:

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

The binary operations and, or, and xor in the pseudocode above denote the integer bitwise AND, bitwise OR, and bitwise XOR operators, respectively; 2^p means 2p (the p-th power of 2).

## 입력

The first line contains two integers p and q (0 ≤ p ≤ 19, 1 ≤ q ≤ 5 · 105) separated by a single space.

The second line contains 2p integers ai (1 ≤ ai ≤ 109) separated by spaces: the items of the array.

Each of the next q lines contains one of the following queries:

• add v δ (0 ≤ v ≤ 2p − 1, 1 ≤ δ ≤ 109)
• sum l r (0 ≤ l ≤ r ≤ 2p − 1)
• and k (0 ≤ k ≤ 2p − 1)
• or k (0 ≤ k ≤ 2p − 1)
• xor k (0 ≤ k ≤ 2p − 1)

## 출력

For each query of type sum, print one integer in a separate line: the answer to this query.

## 예제 입력 1

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


## 예제 출력 1

20
21
9


## 힌트

After the first query, the array becomes 3 4 2 8 5 7 4 2.

After the third query, the array becomes 5 12 0 0 9 9 0 0.

After the fifth query, the array becomes 0 0 9 9 0 0 12 5.