Problem Description

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

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

There are $q$ operations. 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 code is in C++, where count(i) represents the number of $1$s in the binary representation of $i$, for example, count(0) returns $0$, and count(10001279) returns $15$.

The variable v in the above code is the upper bound parameter $v$.

You need to execute the above operations and output the return value of the query() function each time it is executed.

Input Format

Data is read from standard input.

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

The next $q$ lines, each being one of the following:

• 1 u p indicating to execute modify(u, p);
• 2 u indicating to execute query(u) and output a single integer, which is the return value of the function.

Output Format

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

Sample Input and Output

Sample Input #1

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

Sample Output #1

-10
-10

Sample Input #2

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

Sample Output #2

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

Notes/Hints

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 constraints.

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 note the impact of constant factors on program efficiency during implementation.

Hack data has been added.

见题面 Input 部分

见题面 Output 部分