E - Many Operations Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

変数 X と、X の値を変更する N 種類の操作があります。操作 i は整数の組 (T_i,A_i) で表され、意味は次の通りです。

  • T_i=1 のとき、X の値を X\ {\rm and}\ A_i に置き換える。
  • T_i=2 のとき、X の値を X\ {\rm or}\ A_i に置き換える。
  • T_i=3 のとき、X の値を X\ {\rm xor}\ A_i に置き換える。

変数 X を値 C で初期化した状態から、以下の処理を順に実行してください。

  • 操作 1 を行い、操作後の X の値を出力する。
  • 続けて、操作 1,2 を順に行い、操作後の X の値を出力する。
  • 続けて、操作 1,2,3 を順に行い、操作後の X の値を出力する。
  • \vdots
  • 続けて、操作 1,2,\ldots,N を順に行い、操作後の X の値を出力する。
{\rm and}, {\rm or}, {\rm xor} とは 非負整数 A, B の {\rm and}, {\rm or}, {\rm xor} は、以下のように定義されます。
  • A\ {\rm and}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち両方が 1 であれば 1、そうでなければ 0 である。
  • A\ {\rm or}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち少なくとも一方が 1 であれば 1、そうでなければ 0 である。
  • A\ {\rm xor}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうちちょうど一方が 1 であれば 1、そうでなければ 0 である。
例えば、3\ {\rm and}\ 5 = 1、 3\ {\rm or}\ 5 = 7、 3\ {\rm xor}\ 5 = 6 となります。

制約

  • 1 \leq N \leq 2\times 10^5
  • 1\leq T_i \leq 3
  • 0\leq A_i \lt 2^{30}
  • 0\leq C \lt 2^{30}
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N C
T_1 A_1
T_2 A_2
\vdots
T_N A_N

出力

問題文中の指示に従って N 行出力せよ。

入力例 1

3 10
3 3
2 5
1 12

出力例 1

9
15
12

最初、X の値は 10 です。

  • 操作 1 を行うと X の値は 9 になります。
  • 続けて操作 1 を行うと X の値は 10 になり、さらに操作 2 を行うと 15 になります。
  • 続けて操作 1 を行うと X の値は 12 になり、さらに操作 2 を行うと 13 に、さらに続けて操作 3 を行うと 12 になります。

入力例 2

9 12
1 1
2 2
3 3
1 4
2 5
3 6
1 7
2 8
3 9

出力例 2

0
2
1
0
5
3
3
11
2

Score : 500 points

Problem Statement

We have a variable X and N kinds of operations that change the value of X. Operation i is represented as a pair of integers (T_i,A_i), and is the following operation:

  • if T_i=1, it replaces the value of X with X\ {\rm and}\ A_i;
  • if T_i=2, it replaces the value of X with X\ {\rm or}\ A_i;
  • if T_i=3, it replaces the value of X with X\ {\rm xor}\ A_i.

Initialize X with the value of C and execute the following procedures in order:

  • Perform Operation 1, and then print the resulting value of X.
  • Next, perform Operation 1, 2 in this order, and then print the value of X.
  • Next, perform Operation 1, 2, 3 in this order, and then print the value of X.
  • \vdots
  • Next, perform Operation 1, 2, \ldots, N in this order, and then print the value of X.
What are {\rm and}, {\rm or}, {\rm xor}?

The {\rm and}, {\rm or}, {\rm xor} of non-negative integers A and B are defined as follows:

  • When A\ {\rm and}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if both of the digits in that place of A and B are 1, and 0 otherwise.
  • When A\ {\rm or}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if at least one of the digits in that place of A and B is 1, and 0 otherwise.
  • When A\ {\rm xor}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of the digits in that place of A and B is 1, and 0 otherwise.
For example, 3\ {\rm and}\ 5 = 1, 3\ {\rm or}\ 5 = 7, and 3\ {\rm xor}\ 5 = 6.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • 1\leq T_i \leq 3
  • 0\leq A_i \lt 2^{30}
  • 0\leq C \lt 2^{30}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N C
T_1 A_1
T_2 A_2
\vdots
T_N A_N

Output

Print N lines, as specified in the Problem Statement.

Sample Input 1

3 10
3 3
2 5
1 12

Sample Output 1

9
15
12

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