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 \geq 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 \leq t_1 \leq 3, 1 \leq t_2 \leq 4, 1 \leq t_3 \leq 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| \leq 10^9~.

Explanation of ~t_2~

• If a test case has ~t_2 = 1~, then ~0 \leq b,k \leq 30~.
• If a test case has ~t_2 = 2~, then ~0 \leq b,k \leq 100~.
• If a test case has ~t_2 = 3~, then ~0 \leq b,k \leq n~.
• If a test case has ~t_2 = 4~, then ~0 \leq b,k \leq 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 \leq~	~t_1~	~t_2~	~t_3~
1	~10~	3	1	2
2	~100~		2
3	~2\,000~
4	~4\,000~	1	3
5	~6\,000~	3		1
6	~8\,000~	2		2
7	~9\,000~	3	4
8	~10\,000~		3
9	~30\,000~		4
10	~50\,000~			1
11	~60\,000~		3	2
12	~65\,000~	2	4
13	~70\,000~	3
14	~200\,000~
15	~300\,000~	2
16	~400\,000~	3
17	~500\,000~		3
18	~600\,000~		4
19	~700\,000~
20	~800\,000~	1
21	~900\,000~	2
22	~930\,000~	3	3
23	~960\,000~		4	1
24	~990\,000~		3	2
25	~1\,000\,000~		4