There is an integer , initially zero.
There are operations. Each operation is one of the following types:
1 a b
: Add to where is an integer (that can be negative) and is a non-negative integer.2 k
: Write in binary, and compute the value of the digit corresponding to a weight of .
It is guaranteed that at any time.
Input Specification
The first line of the input consists of four integers, .
In the following lines, each line describes an operation.
Two adjacent elements in a line are separated by exactly one space.
Output Specification
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
.
Sample 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
Sample Output
0
1
0
1
0
Additional Samples
Constraints
For all test cases, .
Explanation of
- If a test case has , then .
- If a test case has , then .
- If a test case has , then .
Explanation of
- If a test case has , then .
- If a test case has , then .
- If a test case has , then .
- If a test case has , then .
Explanation of
- If , then all queries are after updates.
- If , then there are no additional constraints.
Test case | ||||
---|---|---|---|---|
1 | 3 | 1 | 2 | |
2 | 2 | |||
3 | ||||
4 | 1 | 3 | ||
5 | 3 | 1 | ||
6 | 2 | 2 | ||
7 | 3 | 4 | ||
8 | 3 | |||
9 | 4 | |||
10 | 1 | |||
11 | 3 | 2 | ||
12 | 2 | 4 | ||
13 | 3 | |||
14 | ||||
15 | 2 | |||
16 | 3 | |||
17 | 3 | |||
18 | 4 | |||
19 | ||||
20 | 1 | |||
21 | 2 | |||
22 | 3 | 3 | ||
23 | 4 | 1 | ||
24 | 3 | 2 | ||
25 | 4 |
Comments