Question
Game of Bits
We have a variable X and N operations that change the value of X. i- th Operation contains a pair of integers (Ti, Ai), and is the following operation: 1. if Ti=1, then X = X and Ai. 2. if Ti=2, then X = X or Ai. 3. if Ti=3, then X = X xor Ai. Initially X = C and execute the all the operations in order. What are and, or, xor? The and, or, xor of non- negative integers A and B are defined as follows: a) When A and B is written in base two, the digit in the 2k's place (k≥0) is 1 if both of the digits in that place of A and B are 1, and 0 otherwise. b) When A or B is written in base two, the digit in the 2k's place (k≥0) is 1 if at least one of the digits in that place of A and B is 1, and 0 otherwise. c) When A xor B is written in base two, the digit in the 2k's place (k≥0) is 1 if exactly one of the digits in that place of A and B is 1, and 0 otherwise. For example, 3 and 5=1, 3 or 5=7, and 3 xor 5=6.
Input
The first line of the input contains 2 integers N and C.
The next N lines contains 2 integers Ti and Ai.
Constraints:
1 <= N <= 2*10^5
1 <= Ti <= 3
0 <= Ai <2^30
0 <= C <2^30
All values in input are integers.
The next N lines contains 2 integers Ti and Ai.
Constraints:
1 <= N <= 2*10^5
1 <= Ti <= 3
0 <= Ai <2^30
0 <= C <2^30
All values in input are integers.
Output
Print N lines, as specified in the Problem Statement.
Example
Sample Input 1:
3 10
3 3
2 5
1 12
Sample Output 1:
9
15
12
Explanation 1:
The initial value of X is 10.
Operation 1 changes X to 9.
Next, Operation 1 changes X to 10, and then Operation 2 changes it to 15.
Next, Operation 1 changes X to 12, and then Operation 2 changes it to 13, and then Operation 3 changes it to 12.
Sample Input 2:
9 12
1 1
2 2
3 3
1 4
2 5
3 6
1 7
2 8
3 9
Sample Output 2:
0
2
1
0
5
3
3
11
2
3 10
3 3
2 5
1 12
Sample Output 1:
9
15
12
Explanation 1:
The initial value of X is 10.
Operation 1 changes X to 9.
Next, Operation 1 changes X to 10, and then Operation 2 changes it to 15.
Next, Operation 1 changes X to 12, and then Operation 2 changes it to 13, and then Operation 3 changes it to 12.
Sample Input 2:
9 12
1 1
2 2
3 3
1 4
2 5
3 6
1 7
2 8
3 9
Sample Output 2:
0
2
1
0
5
3
3
11
2