P3822 [NOI2017] Integer

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...

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.

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.

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

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} | Test point ID | $n \le$ | $t_1$ | $t_2$ | $t_3$ | |:-:|:-:|:-:|:-:|:-:| | $1$ | $10$ | $3$ | $1$ | $2$ | | $2$ | $100$ | $3$ | $2$ | $2$ | | $3$ | $2000$ | $3$ | $2$ | $2$ | | $4$ | $4000$ | $1$ | $3$ | $2$ | | $5$ | $6000$ | $3$ | $3$ | $1$ | | $6$ | $8000$ | $2$ | $3$ | $2$ | | $7$ | $9000$ | $3$ | $4$ | $2$ | | $8$ | $10000$ | $3$ | $3$ | $2$ | | $9$ | $30000$ | $3$ | $4$ | $2$ | | $10$ | $50000$ | $3$ | $4$ | $1$ | | $11$ | $60000$ | $3$ | $3$ | $2$ | | $12$ | $65000$ | $2$ | $4$ | $2$ | | $13$ | $70000$ | $3$ | $4$ | $2$ | | $14$ | $200000$ | $3$ | $4$ | $2$ | | $15$ | $300000$ | $2$ | $4$ | $2$ | | $16$ | $400000$ | $3$ | $4$ | $2$ | | $17$ | $500000$ | $3$ | $3$ | $2$ | | $18$ | $600000$ | $3$ | $4$ | $2$ | | $19$ | $700000$ | $3$ | $4$ | $2$ | | $20$ | $800000$ | $1$ | $4$ | $2$ | | $21$ | $900000$ | $2$ | $4$ | $2$ | | $22$ | $930000$ | $3$ | $3$ | $2$ | | $23$ | $960000$ | $3$ | $4$ | $1$ | | $24$ | $990000$ | $3$ | $3$ | $2$ | | $25$ | $1000000$ | $3$ | $4$ | $2$ | Translated by ChatGPT 5