Given an integer $x=0$, there are two types of queries, each falling into one of the following categories:
- `1 a b`: Add $a \times 2 ^b$ to $x$.
- `2 k`: Find the bit at position $k$ in $x$.
It is guaranteed that $x \ge 0$ at all times.
### Input
- The first line consists of four integers $n, t_1, t_2, t_3$. The meanings of $t_1, t_2, t_3$ are explained below.
- The next $n$ lines, each contains a query in the format described above.
- The numbers on the same line are separated by a space.
### Output
- For each query of type $2$, output the answer on a separate line.
### Example
Input:
```
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:
```
0
1
0
1
0
```
### Constraints
- If $t_1 = 1$, then $a=1$.
- If $t_1 = 2$, then $|a|=1$.
- If $t_1 = 3$, then $|a| \le 10^9$.
- If $t_2 = 1$, then $0 \le b,k \le 30$.
- If $t_2 = 2$, then $0 \le b,k \le 100$.
- If $t_2 = 3$, then $0 \le b,k \le n$.
- If $t_2 = 4$, then $0 \le b,k \le 30n$.
- If $t_3 = 1$, ensure that all queries of type $2$ come after queries of type $1$.
- If $t_3 = 2$, there are no limitations on the order of queries.
| Test | $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 |
