题目背景

破碎的镜面里倒映着破碎的射线；

破碎的文字中隐藏着破碎的——

题目描述

有一个 long long 类型的数组 a[]。

在给出所有操作之前，给定上界参数 $v$。

共有 $q$ 次操作。每次操作为以下两个函数之一：

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;
}

上述程序为 C++ 代码，其中 count(i) 表示 $i$ 二进制下 $1$ 的个数，例如 count(0) 的返回值为 $0$，而 count(10001279) 的返回值为 $15$。

上述程序中出现的变量 v 即上界参数 $v$。

你需要执行上述操作，并在每次执行 query() 函数后，输出函数的返回值。

输入格式

从标准输入中读取数据。

第一行，两个正整数 $q,v$，表示操作数，以及上界参数。

接下来 $q$ 行，每行为以下二者之一：

• 1 u p 表示执行 modify(u,p)；
• 2 u 表示执行 query(u) 并输出一行一个整数，为函数的返回值。

输出格式

在每次执行 query() 函数后，输出函数的返回值。

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

提示

子任务 1（$8$ 分）：$1\leq q\leq 10^3$，$1\leq v\leq 10^4$。

子任务 2（$23$ 分）：$1\leq v\leq 10^5$。

子任务 3（$16$ 分）：$1\leq q\leq 50$。

子任务 4（$28$ 分）：$1\leq q\leq 1000$。

子任务 5（$25$ 分）：无特殊限制。

对于全部数据，$1\leq q\leq 2\times 10^5$，$1\leq u\leq v< 2^{30}$，$-10^4\leq p\leq 10^4$。

请选手注意代码实现时常数因子带来的程序效率上的影响。

已加入 hack 数据。