Integers

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.

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.

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.

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.