【NOI2017】整数
P 博士将他的计算任务抽象为对一个整数的操作。
具体来说，有一个整数 $x$ ，一开始为0。
接下来有 $n$ 个操作，每个操作都是以下两种类型中的一种：
1$a$ $b$ ：将 $x$ 加上整数 $a \cdot 2 ^ b$，其中 $a$ 为一个整数，$b$ 为一个非负整数2$k$ ：询问 $x$ 在用二进制表示时，位权为 $2 ^ k$ 的位的值（即这一位上的 $1$ 代表 $2 ^ k$ ）
保证在任何时候，$x \ge 0$。
输入格式
从标准输入读入数据。
输入的第一行包含四个正整数 $n, t_1, t_2, t_3$，$n$ 的含义见题目描述，$t_1, t_2, t_3$ 的具体含义见子任务。
接下来 $n$ 行，每行给出一个操作，具体格式和含义见题目描述。
同一行输入的相邻两个元素之间，用恰好一个空格隔开。
输出格式
输出到标准输出。
对于每个询问操作，输出一行，表示该询问的答案（0或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
0
1
0
1
0
样例中有 $10$ 个操作： 第 $1$ 个为将 $x$ 加上 $100 \times 2^0$ ，操作后， $x= 100$ ；
第 $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$ 。
样例二
见下载文件中的 ex_integer2.in 与 ex_integer2.ans。
该组样例的数据范围同第7个测试点。
样例三
见下载文件中的 ex_integer3.in 与 ex_integer3.ans。
该组样例的数据范围同第13个测试点。
样例四
见下载文件中的 ex_integer4.in 与 ex_integer4.ans。
该组样例的数据范围同第14个测试点。
限制与约定
在所有测试点中，$1 \le t_1 \le 3, 1 \le t_2 \le 4, 1 \le t_3 \le 2$。 不同的 $t_1, t_2, t_3$ 对应的特殊限制如下：
- 对于 $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$ 的测试点，不保证询问操作和修改操作的先后顺序
本题共25个测试点，每个测试点4分。各个测试点的数据范围如下：
| 测试点编号 | $n \le$ | $t_1$ | $t_2$ | $t_3$ |
|---|---|---|---|---|
| 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 |
时间限制：$2\texttt{s}$
空间限制：$512\texttt{MB}$