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）。 对于加法操作，没有任何输出。

样例一

input

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

output

0
1
0
1
0

explanation

样例中有 $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 30n$
• 对于 $t_3=1$ 的测试点，保证所有询问操作都在所有修改操作之后
• 对于 $t_3=2$ 的测试点，不保证询问操作和修改操作的先后顺序

本题共25个测试点，每个测试点4分。各个测试点的数据范围如下：

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载