Modular Range Update and Query

Given a sequence (a), you are to perform a series of online operations. There are two types of operations:

• Operation \(1\ x\ y\ v\): For every index \(i\) (where \(0 \le i < n\)) satisfying \(i \equiv y \pmod{2^x}\), add \(v\) to \(a_i\).
• Operation \(2\ x\ y\): For every index \(i\) satisfying \(i \equiv y \pmod{2^x}\), output the sum of \(a_i\).

Note: This is an online problem. All operations must be processed in the given order.

inputFormat

The input begins with a line containing two integers (n) and (q), where (n) is the number of elements in the sequence and (q) is the number of operations.

The second line contains (n) integers: (a_0, a_1, \dots, a_{n-1}), representing the initial sequence.

Each of the following (q) lines represents an operation in one of the following formats:

• For an update operation: 1 x y v
• For a query operation: 2 x y

In the update operation, every index \(i\) such that \(i \equiv y \pmod{2^x}\) will have \(v\) added to \(a_i\). In the query operation, you must output the sum of all \(a_i\) for which \(i \equiv y \pmod{2^x}\).

outputFormat

For each query operation (type 2), output a single line containing the sum of the selected elements.

sample

5 5
1 2 3 4 5
2 1 0
1 1 0 10
2 1 0
1 2 1 -2
2 2 1

9
39
0

</p>