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 である。
制約
- 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.
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