There is an integer $x$, initially zero.

There are $n$ operations. Each operation is one of the following types:

• 1 a b: Add $a\cdot 2^b$ to $x$ where $a$ is an integer (that can be negative) and $b$ is a non-negative integer.
• 2 k: Write $x$ in binary, and compute the value of the digit corresponding to a weight of $2^k$.

It is guaranteed that $x\ge 0$ at any time.

Input Specification

The first line of the input consists of four integers, $n,t_1,t_2,t_3$.

In the following $n$ lines, each line describes an operation.

Two adjacent elements in a line are separated by exactly one space.

Output Specification

For each type 2 k query, output a line with an integer (0 or 1) denoting the answer. There shall be no output for each operation of 1 a b.

Sample 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

Sample Output

0
1
0
1
0

Additional Samples

integer.zip

Constraints

For all test cases, $1\le t_1\le 3,1\le t_2\le 4,1\le t_3\le 2$.

Explanation of $t_1$

• If a test case has $t_1=1$, then $a=1$.
• If a test case has $t_1=2$, then $|a|=1$.
• If a test case has $t_1=3$, then $|a|\le {10}^9$.

Explanation of $t_2$

• If a test case has $t_2=1$, then $0\le b,k\le 30$.
• If a test case has $t_2=2$, then $0\le b,k\le 100$.
• If a test case has $t_2=3$, then $0\le b,k\le n$.
• If a test case has $t_2=4$, then $0\le b,k\le 30n$.

Explanation of $t_3$

• If $t_3=1$, then all queries are after updates.
• If $t_3=2$, then there are no additional constraints.

Test case	$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