Description

There is an array a[] of type long long.

Before giving all operations, an upper bound parameter $v$ is given.

There are $q$ operations in total. 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;
}

The above program is C++ code, where count(i) denotes the number of $1$ bits in the binary representation of $i$. For example, count(0) returns $0$, and count(10001279) returns $15$.

The variable v appearing in the program is exactly the upper bound parameter $v$.

You need to execute the operations above, and after each execution of query(), output the return value of the function.

Input Format

Read input from standard input.

The first line contains two positive integers $q, v$, representing the number of operations and the upper bound parameter.

The next $q$ lines are one of the following:

• 1 u p means executing modify(u,p).
• 2 u means executing query(u) and outputting one integer per line, which is the return value of the function.

Output Format

After each execution of query(), output the return value of the function.

7 19
1 3 -8
1 4 8
1 13 -1
2 2
1 1 -10
1 1 8
2 12

-10
-10

29 1066163924
2 680224223
1 440869582 -1203
2 993311885
1 729027357 9874
2 665374856
1 192704973 -9712
1 681750770 -1099
2 239837676
1 938998353 -109
2 174153423
1 781133679 7360
2 522379034
2 125773599
1 483114333 -376
2 723115805
2 699246389
1 527125403 9279
1 930492461 -9753
1 14775627 -3676
1 152692805 5045
1 945645197 2710
2 298593273
1 888744817 2514
1 651751441 4559
2 963653895
1 986621281 -8296
2 10216021
2 848072343
2 482342087

0
-5264389353
181209893739
-398925734374
-431628986929
-73026998100
-298228449649
73714612345
53926122085
97102847037
96145153438
110646771673
199641765482
314932271763

Hint

Subtask 1 ($8$ points): $1\leq q\leq 10^3$, $1\leq v\leq 10^4$.

Subtask 2 ($23$ points): $1\leq v\leq 10^5$.

Subtask 3 ($16$ points): $1\leq q\leq 50$.

Subtask 4 ($28$ points): $1\leq q\leq 1000$.

Subtask 5 ($25$ points): no special restrictions.

For all data, $1\leq q\leq 2\times 10^5$, $1\leq u\leq v< 2^{30}$, $-10^4\leq p\leq 10^4$.

Please pay attention to the impact of constant factors on program efficiency when implementing the code.

Hack testdata has been added.

Translated by ChatGPT 5