Yet_another_queries — OOI qualification
Task type: batch | Time limit: 1.5 s | Memory limit: 256 MB | Difficulty: 24
Algorithms: range queries, segment tree, bitmask, divide and conquer

# Yet another queries

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | standard output |
| Time limit:   | 1.5 seconds     |
| Memory limit: | 256 megabytes   |

You are given an array $a_0, a_1, ..., a_{2^n-1}$ consisting of $2^n$ elements. Note that the elements are numbered from zero.

You have to process $q$ queries to this array of two types:

- `1 l r k v`. In this case, the elements $a_{l \oplus k}, a_{(l+1) \oplus k}, ..., a_{r \oplus k}$ are replaced with $v$.
- `2 l r k`. In this case, you need to calculate the sum $a_{l \oplus k} + a_{(l+1) \oplus k} + ... + a_{r \oplus k}$.

Here $ \oplus $ denotes the bitwise XOR operation.

### Input

The first line contains a single integer $n$ ($0 \le n \le 20$).

The second line contains $2^n$ integers $a_0, a_1, ..., a_{2^n-1}$ ($0 \le a_i \le 10^7$) – the elements of the array.

The third line contains a single integer $q$ ($1 \le q \le 10^6$) – the number of queries.

The next $q$ lines contain the query descriptions. The $i$-th line contains an integer $t_i$ ($1 \le t_i \le 2$).

- If $t_i = 1$, then the line contains four integers $l_i, r_i, k_i,$ and $v_i$ ($0 \le l_i \le r_i < 2^n, 0 \le k_i < 2^n, 0 \le v_i \le 10^9$). In this case, we need to assign the value $v_i$ to each of the elements $a_{l_i \oplus k_i}, a_{(l_i+1) \oplus k_i}, ..., a_{r_i \oplus k_i}$.
- If $t_i = 2$, then the line contains three integers $l_i, r_i$, and $k_i$ ($0 \le l_i \le r_i < 2^n, 0 \le k_i < 2^n$). In this case, we need to calculate the sum $a_{l_i \oplus k_i} + a_{(l_i+1) \oplus k_i} + ... + a_{r_i \oplus k_i}$.

### Output

For each query of the second type, print the desired sum.

### Example

| standard input  | standard output |
|-----------------|-----------------|
| 3               | 22              |
| 1 5 8 4 3 7 8 4 |                 |
| 3               | 26              |
| 2 4 7 1         |                 |
| 1 1 5 3 8       |                 |
| 2 4 7 1         |                 |

#### Note

In the first query, $a_{4 \oplus 1} + a_{5 \oplus 1} + a_{6 \oplus 1} + a_{7 \oplus 1} = a_5 + a_4 + a_7 + a_6 = 22$.

In the second query, we need to replace elements $a_{1 \oplus 3}, a_{2 \oplus 3}, a_{3 \oplus 3}, a_{4 \oplus 3}$ and $a_{5 \oplus 3}$ with 8. The array after these changes will be 8, 8, 8, 4, 3, 7, 8, 8.

In the last query, $a_{4 \oplus 1} + a_{5 \oplus 1} + a_{6 \oplus 1} + a_{7 \oplus 1} = 26$.

## Scoring

The tests for this problem consist of 8 groups. Points for each group are awarded only if all the tests in that group and some tests from the previous groups pass. Offline-testing means that the results of testing your solution on this group will only be available after the competition ends.

| Group | Score | Additional constraints |   |   |   | Required groups | Comment |
|-------|-------|------------------------|---|---|---|-----------------|-------------------------------------------------------------|
|       |       | $n$ | $q$ | $a_i$ | $v_i$ |  | |
| 0     | 0     | - | - | - | - | - | Samples. |
| 1     | 19    | $n \le 10$ | $q \le 1000$ | - | - | 0 |  |
| 2     | 17    | $n \le 17$ | $q \le 200\ 000$ | - | - | - | $k_i$ is a power of two. If $t_i = 1$, then $l_i = r_i$ |
| 3     | 11    | - | - | $a_i \le 1$ | - | - | $t_i = 2$ |
| 4     | 13    | - | - | $a_i \le 1$ | $v_i \le 1$ | 3 |  |
| 5     | 12    | $n \le 17$ | $q \le 200\ 000$ | - | - | - | $t_i = 2$ |
| 6     | 9     | $n \le 17$ | $q \le 200\ 000$ | - | - | 2 | If $t_i = 1$, then $l_i = r_i$ |
| 7     | 10    | $n \le 17$ | $q \le 200\ 000$ | - | - | 0, 1, 2, 5, 6 |  |
| 8     | 9     | - | - | - | - | 0 – 7 | **Offline-testing.** |

Starter code: