A - XOR Circle 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

すぬけ君は N 枚の帽子を持っています。i 枚目の帽子には整数 a_i が書かれています。

N 頭のラクダが円環状に並んでいます。 すぬけ君はそれぞれのラクダに 1 枚の帽子を被せようとしています。

どのラクダについても以下の条件が成立するような帽子の被せ方が存在するならば Yes を、そうでなければ No を出力してください。

  • 両隣のラクダが被っている帽子に書かれた数のビットごとの排他的論理和が自身の被っている帽子に書かれた数と等しい
ビットごとの排他的論理和について

n 個の非負整数 x_1,x_2, \ldots, x_n の排他的論理和 x_1 \oplus x_2 \oplus \ldots \oplus x_n は以下のように定義されます。

  • x_1 \oplus x_2 \oplus \ldots \oplus x_n を二進表記した際の 2^k(k \geq 0) の位の数は x_1,x_2, \ldots, x_n のうち、二進表記した際の 2^k(k \geq 0) の位の数が 1 となるものの個数が奇数ならば 1、そうでなければ 0 となる。
例えば、3 \oplus 5 = 6 となります。

制約

  • 入力は全て整数
  • 3 \leq N \leq 10^{5}
  • 0 \leq a_i \leq 10^{9}

入力

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

N
a_1 a_2 \ldots a_{N}

出力

答えを出力せよ。

入力例 1

3
1 2 3

出力例 1

Yes
  • 1,2,3 が書かれた帽子を時計回りに被せたとき、どのラクダも問題文中の条件を満たすため、答えは Yes となります。

入力例 2

4
1 2 4 8

出力例 2

No
  • そのような被せ方は存在しません。よって、答えは No となります。

Score : 300 points

Problem Statement

Snuke has N hats. The i-th hat has an integer a_i written on it.

There are N camels standing in a circle. Snuke will put one of his hats on each of these camels.

If there exists a way to distribute the hats to the camels such that the following condition is satisfied for every camel, print Yes; otherwise, print No.

  • The bitwise XOR of the numbers written on the hats on both adjacent camels is equal to the number on the hat on itself.
What is XOR? The bitwise XOR x_1 \oplus x_2 \oplus \ldots \oplus x_n of n non-negative integers x_1, x_2, \ldots, x_n is defined as follows: - When x_1 \oplus x_2 \oplus \ldots \oplus x_n is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if the number of integers among x_1, x_2, \ldots, x_n whose binary representations have 1 in the 2^k's place is odd, and 0 if that count is even. For example, 3 \oplus 5 = 6.

Constraints

  • All values in input are integers.
  • 3 \leq N \leq 10^{5}
  • 0 \leq a_i \leq 10^{9}

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_{N}

Output

Print the answer.

Sample Input 1

3
1 2 3

Sample Output 1

Yes
  • If we put the hats with 1, 2, and 3 in this order, clockwise, the condition will be satisfied for every camel, so the answer is Yes.

Sample Input 2

4
1 2 4 8

Sample Output 2

No
  • There is no such way to distribute the hats; the answer is No.