/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 266 点
問題文
高橋君は、N 台のサーバーを経由してデータを送信する暗号化システムを設計しています。
このシステムでは、N 台のサーバーが一列に接続されており、左から順に 1, 2, \ldots, N の番号が付けられています。各サーバー i（1 \leq i \leq N）には暗号化キー A_i（非負整数）が設定されています。
データ送信に先立ち、各サーバーが実際に使用する暗号化キー B_i が以下のルールで決まります。B_i の値は元の暗号化キー A_1, A_2, \ldots, A_N のみに基づいて決定され、すべてのサーバーについて同時に確定します。
- サーバー j（2 \leq j \leq N-1）が次の条件を満たすとき、サーバー j を「挟まれた異常サーバー」と呼びます：A_{j-1} = A_{j+1} かつ A_{j-1} \neq A_j が成り立つ。すなわち、両隣のサーバーの暗号化キーが等しく、かつ自身の暗号化キーがそれらと異なる場合です。
- 「挟まれた異常サーバー」と判定されたサーバー j については B_j = 0 とします。
- それ以外のサーバー j（サーバー 1、サーバー N、および上記の条件を満たさないサーバー）については B_j = A_j とします。
次に、非負整数のデータ X が以下のルールで左から右へ送信されます。ここで D_0 = X とし、各サーバー i（i = 1, 2, \ldots, N の順に）は、データ D_{i-1} を受け取り、D_i = D_{i-1} \oplus B_i（\oplus はビットごとの排他的論理和）を計算します。サーバー 1 が受け取るデータ D_0 は高橋君から送信されたデータ X そのものであり、サーバー N が計算した D_N が最終的な出力データです。
高橋君がサーバー 1 に送信するデータ X と、各サーバーの暗号化キーが与えられたとき、最終的な出力データ D_N を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq X \leq 10^9
- 0 \leq A_i \leq 10^9（1 \leq i \leq N）
- 入力は全て整数
入力
N X A_1 A_2 \ldots A_N
- 1 行目には、サーバーの台数を表す整数 N と、高橋君が最初に送信するデータを表す非負整数 X が、スペース区切りで与えられる。
- 2 行目には、各サーバー i（1 \leq i \leq N）の暗号化キーを表す非負整数 A_i が、スペース区切りで N 個与えられる。
出力
最終的な出力データを 1 行で出力せよ。
入力例 1
5 10 1 2 1 3 3
出力例 1
10
入力例 2
3 5 7 7 7
出力例 2
2
入力例 3
8 123 8 1 8 3 3 5 7 5
出力例 3
123
入力例 4
20 999999999 0 1000000000 0 5 5 7 8 7 3 3 3 9 1 9 4 6 4 2 2 2
出力例 4
999999998
入力例 5
1 0 0
出力例 5
0
Score : 266 pts
Problem Statement
Takahashi is designing an encryption system that transmits data through N servers.
In this system, N servers are connected in a line, numbered 1, 2, \ldots, N from left to right. Each server i (1 \leq i \leq N) has an encryption key A_i (a non-negative integer) assigned to it.
Prior to data transmission, the encryption key B_i that each server actually uses is determined by the following rules. The value of B_i is determined solely based on the original encryption keys A_1, A_2, \ldots, A_N, and is finalized simultaneously for all servers.
- A server j (2 \leq j \leq N-1) is called a "sandwiched anomalous server" if it satisfies the following condition: A_{j-1} = A_{j+1} and A_{j-1} \neq A_j. In other words, the encryption keys of both neighboring servers are equal, and its own encryption key differs from theirs.
- For a server j that is determined to be a "sandwiched anomalous server", B_j = 0.
- For all other servers j (server 1, server N, and servers that do not satisfy the above condition), B_j = A_j.
Next, non-negative integer data X is transmitted from left to right according to the following rules. Let D_0 = X, and each server i (in order i = 1, 2, \ldots, N) receives data D_{i-1} and computes D_i = D_{i-1} \oplus B_i (\oplus denotes the bitwise exclusive OR). The data D_0 received by server 1 is the data X sent by Takahashi, and D_N computed by server N is the final output data.
Given the data X that Takahashi sends to server 1 and the encryption key of each server, find the final output data D_N.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq X \leq 10^9
- 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All input values are integers
Input
N X A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of servers and a non-negative integer X representing the data Takahashi initially sends, separated by a space.
- The second line contains N non-negative integers A_i representing the encryption key of each server i (1 \leq i \leq N), separated by spaces.
Output
Print the final output data on a single line.
Sample Input 1
5 10 1 2 1 3 3
Sample Output 1
10
Sample Input 2
3 5 7 7 7
Sample Output 2
2
Sample Input 3
8 123 8 1 8 3 3 5 7 5
Sample Output 3
123
Sample Input 4
20 999999999 0 1000000000 0 5 5 7 8 7 3 3 3 9 1 9 4 6 4 2 2 2
Sample Output 4
999999998
Sample Input 5
1 0 0
Sample Output 5
0