Array Modification with Binary Step Increments

You are given an array a[] of type long long (initially all zeros) and an upper bound parameter v. Then, there will be q operations provided. Each operation is one of the following two functions:

void modify(int u, int p) {
    for (int i = u; i <= v; i += count(i))
        a[i] += p;
}
long long query(long long u) {
long long ret = 0;
for (int i = u; i <= v; i += count(i))
ret += a[i];
return ret;
}

Here, count(i) is defined as the number of 1's in the binary representation of i. In particular, \(count(0)=0\) and for example \(count(10001279)=15\). For each query() operation, you are required to output its returned value.

The operations are provided using the following format:

• For a modify operation, the input line is: 1 u p, which corresponds to calling modify(u, p).
• For a query operation, the input line is: 2 u, which corresponds to calling query(u).

inputFormat

The first line contains two space‐separated integers v and q, where v is the upper bound of the array indices (array indices are from 1 to v) and q is the number of operations.

The next q lines each contain an operation in one of the following formats:

• 1 u p: A modify operation, which calls modify(u, p).
• 2 u: A query operation, which calls query(u) and requires output.

outputFormat

For each query operation, output a single line containing the result of that query.

sample

10 3
1 1 5
2 1
2 2

30
25

</p>