# #2302. 「NOI2017」整数

#### 题目描述

P 博士将他的计算任务抽象为对一个整数的操作。

• 1 $a$ $b$ ：将 $x$ 加上整数 $a \cdot 2 ^ b$，其中 $a$ 为一个整数，$b$ 为一个非负整数

• 2 $k$ ：询问 $x$ 在用二进制表示时，位权为 $2 ^ k$ 的位的值（即这一位上的 $1$ 代表 $2 ^ k$

#### 样例输入 1

10 3 1 2
1 100 0
1 2333 0
1 -233 0
2 5
2 7
2 15
1 5 15
2 15
1 -1 12
2 15

#### 样例输出 1

0
1
0
1
0

#### 样例解释 1

$2$ 个为将 $x$ 加上 $2333 \times 2^0$ ，操作后， $x= 2433$

$3$ 个为将 $x$ 加上 $-233 \times 2^0$ ，操作后， $x= 2200$

$4$ 个为询问 $x$ 位权为 $2^5$ 的位上的值， $x$ 在二进制下为 $100010011000$ ，答案为 $0$

$5$ 个为询问 $x$ 位权为 $2^7$ 的位上的值， $x$ 在二进制下为 $100010011000$ ，答案为 $1$

$6$ 个为询问 $x$ 位权为 $2^{15}$ 的位上的值， $x$ 在二进制下为 $100010011000$ ，答案为 $0$

$7$ 个为将 $x$ 加上 $5 \times 2^{15} = 163840$ ，操作后， $x= 166040$

$8$ 个为询问 $x$ 位权为 $2^{15}$ 的位上的值， $x$ 在二进制下为 $101000100010011000$ ，答案为 $1$

$9$ 个为将 $x$ 加上 $-1 \times 2^{12} = -4096$ ，操作后， $x= 161944$

$10$ 个为询问 $x$ 位权为 $2^{15}$ 的位上的值， $x$ 在二进制下为 $100111100010011000$ ，答案为 $0$

### 子任务

• 对于 $t_1 = 1$ 的测试点，满足 $a = 1$

• 对于 $t_1 = 2$ 的测试点，满足 $|a| = 1$

• 对于 $t_1 = 3$ 的测试点，满足 $|a| \le 10 ^ 9$

• 对于 $t_2 = 1$ 的测试点，满足 $0 \le b,k \le 30$

• 对于 $t_2 = 2$ 的测试点，满足 $0 \le b,k \le 100$

• 对于 $t_2 = 3$ 的测试点，满足 $0 \le b,k \le n$

• 对于 $t_2 = 4$ 的测试点，满足 $0 \le b,k \le 30 n$

• 对于 $t_3 = 1$ 的测试点，保证所有询问操作都在所有修改操作之后

• 对于 $t_3 = 2$ 的测试点，不保证询问操作和修改操作的先后顺序

$1$ $10$ $3$ $1$ $2$
$2$ $100$ $2$
$3$ $2000$
$4$ $4000$ $1$ $3$
$5$ $6000$ $3$ $1$
$6$ $8000$ $2$ $2$
$7$ $9000$ $3$ $4$
$8$ $10000$ $3$
$9$ $30000$ $4$
$10$ $50000$ $1$
$11$ $60000$ $3$ $2$
$12$ $65000$ $2$ $4$
$13$ $70000$ $3$
$14$ $200000$
$15$ $300000$ $2$
$16$ $400000$ $3$
$17$ $500000$ $3$
$18$ $600000$ $4$
$19$ $700000$
$20$ $800000$ $1$
$21$ $900000$ $2$
$22$ $930000$ $3$ $3$
$23$ $960000$ $4$ $1$
$24$ $990000$ $3$ $2$
$25$ $1000000$ $4$