Dr. P has abstracted his computational task into operations on an integer. Specifically, there is an integer $x$, which is initially $0$. There are $n$ operations, each of which is one of the following two types:

• $1 \ a \ b$: Add the integer $a \cdot 2^b$ to $x$, where $a$ is an integer and $b$ is a non-negative integer.
• $2 \ k$: Query the value of the bit with weight $2^k$ in the binary representation of $x$ (i.e., the $1$ at this position represents $2^k$).

It is guaranteed that $x \ge 0$ at all times.

Input

The input is read from the file integer.in. The first line of the input contains four positive integers $n, t_1, t_2, t_3$. The meaning of $n$ is described above, and the specific meanings of $t_1, t_2, t_3$ are described in the Subtasks section. The next $n$ lines each describe an operation, with the format and meaning as described above. Adjacent elements on the same line are separated by exactly one space.

Output

The output is written to the file integer.out. For each query operation, output one line representing the answer to the query ($0$ or $1$). For addition operations, there is no output.

Examples

Input 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

Output 1

0
1
0
1
0

Note 1

There are 10 operations in the example: The 1st operation adds $100 \times 2^0$ to $x$, after which $x = 100$. The 2nd operation adds $2333 \times 2^0$ to $x$, after which $x = 2433$. The 3rd operation adds $-233 \times 2^0$ to $x$, after which $x = 2200$. The 4th operation queries the bit with weight $2^5$ of $x$. In binary, $x$ is $100010011000$, so the answer is $0$. The 5th operation queries the bit with weight $2^7$ of $x$. In binary, $x$ is $100010011000$, so the answer is $1$. The 6th operation queries the bit with weight $2^{15}$ of $x$. In binary, $x$ is $100010011000$, so the answer is $0$. The 7th operation adds $5 \times 2^{15} = 163840$ to $x$, after which $x = 166040$. The 8th operation queries the bit with weight $2^{15}$ of $x$. In binary, $x$ is $101000100010011000$, so the answer is $1$. The 9th operation adds $-1 \times 2^{12} = -4096$ to $x$, after which $x = 161944$. The 10th operation queries the bit with weight $2^{15}$ of $x$. In binary, $x$ is $100111100010011000$, so the answer is $0$.

Input 2

(See integer/integer2.in)

Output 2

(See integer/integer2.ans)

Note 2

This example corresponds to the data range of the 7th test case.

Input 3

(See integer/integer3.in)

Output 3

(See integer/integer3.ans)

Note 3

This example corresponds to the data range of the 13th test case.

Input 4

(See integer/integer4.in)

Output 4

(See integer/integer4.ans)

Note 4

This example corresponds to the data range of the 14th test case.

Subtasks

In all test cases, $1 \le t_1 \le 3, 1 \le t_2 \le 4, 1 \le t_3 \le 2$. The specific constraints corresponding to different $t_1, t_2, t_3$ are as follows:

• For test cases with $t_1 = 1$, $a = 1$.
• For test cases with $t_1 = 2$, $|a| = 1$.
• For test cases with $t_1 = 3$, $|a| \le 10^9$.
• For test cases with $t_2 = 1$, $0 \le b, k \le 30$.
• For test cases with $t_2 = 2$, $0 \le b, k \le 100$.
• For test cases with $t_2 = 3$, $0 \le b, k \le n$.
• For test cases with $t_2 = 4$, $0 \le b, k \le 30n$.
• For test cases with $t_3 = 1$, it is guaranteed that all query operations occur after all modification operations.
• For test cases with $t_3 = 2$, the order of query and modification operations is not guaranteed.

There are 25 test cases in total, each worth 4 points. The data ranges for each test case are as follows: