Codeforces Round 665 (Div. 2) |
---|
Finished |
You are given an array $$$a$$$ of length $$$2^n$$$. You should process $$$q$$$ queries on it. Each query has one of the following $$$4$$$ types:
Write a program that can quickly process given queries.
The first line contains two integers $$$n$$$, $$$q$$$ ($$$0 \le n \le 18$$$; $$$1 \le q \le 10^5$$$) — the length of array $$$a$$$ and the number of queries.
The second line contains $$$2^n$$$ integers $$$a_1, a_2, \ldots, a_{2^n}$$$ ($$$0 \le a_i \le 10^9$$$).
Next $$$q$$$ lines contains queries — one per line. Each query has one of $$$4$$$ types:
It is guaranteed that there is at least one $$$Sum$$$ query.
Print the answer for each $$$Sum$$$ query.
2 3 7 4 9 9 1 2 8 3 1 4 2 4
24
3 8 7 0 8 8 7 1 5 2 4 3 7 2 1 3 2 4 1 6 2 3 1 5 16 4 8 8 3 0
29 22 1
In the first sample, initially, the array $$$a$$$ is equal to $$$\{7,4,9,9\}$$$.
After processing the first query. the array $$$a$$$ becomes $$$\{7,8,9,9\}$$$.
After processing the second query, the array $$$a_i$$$ becomes $$$\{9,9,7,8\}$$$
Therefore, the answer to the third query is $$$9+7+8=24$$$.
In the second sample, initially, the array $$$a$$$ is equal to $$$\{7,0,8,8,7,1,5,2\}$$$. What happens next is:
Name |
---|