Background

At the summit of human wisdom, there is a supercomputer with a word length of $1\,048\,576$ bits (this number is irrelevant to solving the problem). Dr. P, a famous theoretical computer scientist, is using it for various research. Unfortunately, a typhoon cut off the power system today, and the supercomputer cannot work. Dr. P needs to submit the experimental results tomorrow, so he has to ask you, who have studied OI, for help...

Problem Description

Dr. P abstracts his computation task as operations on an integer.

Specifically, there is an integer $x$, initially $0$.

Then there are $n$ operations, each 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 nonnegative integer.
• 2 k: ask for the value of the bit of $x$ in binary whose weight is $2^k$ (that is, a $1$ in this bit represents $2^k$).

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

Input Format

The first line of input contains four positive integers $n, t_1, t_2, t_3$. The meaning of $n$ is given in the problem statement, and the meanings of $t_1, t_2, t_3$ are given in the subtasks.

Then follow $n$ lines, each giving one operation. The specific format and meaning are as described above.

Output Format

For each query operation, output one line representing the answer ($0$ or $1$). For addition operations, there is no output.

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

0
1
0
1
0

Hint

In all test points, $1 \leqslant t_1 \leqslant 3$, $1 \leqslant t_2 \leqslant 4$, $1 \leqslant t_3 \leqslant 2$. Different pairs $t_1, t_2, t_3$ correspond to the following special restrictions:

• For $t_1 = 1$, $a = 1$.
• For $t_1 = 2$, $|a| = 1$.
• For $t_1 = 3$, $|a| \leqslant 10^9$.
• For $t_2 = 1$, $0 \leqslant b, k \leqslant 30$.
• For $t_2 = 2$, $0 \leqslant b, k \leqslant 100$.
• For $t_2 = 3$, $0 \leqslant b, k \leqslant n$.
• For $t_2 = 4$, $0 \leqslant b, k \leqslant 30n$.
• For $t_3 = 1$, all query operations appear after all addition operations.
• For $t_3 = 2$, the order between query operations and addition operations is not guaranteed.

There are 25 test points in total, each worth 4 points. The Constraints of each test point are as follows:

::cute-table{tuack}

Translated by ChatGPT 5