정수

정수 $x$가 있으며, 처음에는 $0$이다.

$n$개의 연산이 주어진다. 각 연산은 다음 두 종류 중 하나이다.

• 1 a b: $x$에 $a \cdot 2^b$를 더한다. 여기서 $a$는 음수일 수 있는 정수이고, $b$는 음이 아닌 정수이다.
• 2 k: $x$를 이진수로 나타냈을 때, 가중치 $2^k$의 자리에 있는 숫자를 구한다.

모든 시점에서 $x \geq 0$이 보장된다.

첫째 줄에 네 정수 $n$, $t_1$, $t_2$, $t_3$가 주어진다.

이어지는 $n$개의 줄에 연산이 하나씩 주어진다. 한 줄에서 인접한 두 원소는 공백 한 칸으로 구분된다.

2 k 형태의 질의마다 답(0 또는 1)을 한 줄에 하나씩 출력한다. 1 a b 연산에 대해서는 출력하지 않는다.

모든 테스트 케이스에 대해 $1 \leq t_1 \leq 3$, $1 \leq t_2 \leq 4$, $1 \leq t_3 \leq 2$이다.

$t_1$의 의미

• $t_1 = 1$이면 $a = 1$이다.
• $t_1 = 2$이면 $|a| = 1$이다.
• $t_1 = 3$이면 $|a| \leq 10^9$이다.

$t_2$의 의미

• $t_2 = 1$이면 $0 \leq b, k \leq 30$이다.
• $t_2 = 2$이면 $0 \leq b, k \leq 100$이다.
• $t_2 = 3$이면 $0 \leq b, k \leq n$이다.
• $t_2 = 4$이면 $0 \leq b, k \leq 30n$이다.

$t_3$의 의미

• $t_3 = 1$이면 모든 질의는 갱신 연산 뒤에 온다.
• $t_3 = 2$이면 추가 제약은 없다.