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