Four XOR

Time limit1sMemory limit256 MB

Summary

Given n distinct integers, decide whether four of them can be chosen so that their bitwise XOR is zero.

Level: Medium7 of 10
Topics: Bit manipulation, Brute force, Combinatorics, Hash map
Solved: No attempts yet

Problem

Given a sequence $A_{1...n}$ of distinct integers, determine whether there exist four indices $x, y, z, w$ such that $1 \le x < y < z < w \le n$ and $A_x \oplus A_y \oplus A_z \oplus A_w = 0$ .

Here $x \oplus y$ is the bitwise exclusive-or of $x$ and $y$ , sometimes written $x \mathrm{xor} y$ .

Input

The first line contains a single integer $n$ ( $4 \le n \le 10^5$ ).

The second line contains $n$ integers $A_{1...n}$ ( $0 \le A_i \le 10^5$ ). All $A_i$ are guaranteed to be distinct.

Output

Output "Yes" if four indices satisfying the conditions exist, or "No" otherwise.

Examples3

Example 1
Input
```
5
1 2 3 4 5
```
Expected output
```
Yes
```
Example 2
Input
```
5
1 2 4 8 16
```
Expected output
```
No
```
Example 3
Input
```
5
1 3 4 8 9
```
Expected output
```
No
```