XOR 합 최대화

시간 제한1초메모리 제한256 MB

요약

주어진 정수들에서 비어 있지 않은 부분집합을 골라 그 수들의 xor이 최대가 되도록 합니다.

난이도: 보통10점 중 7점
유형: 비트 연산, 그리디
정답자: 아직 제출이 없습니다

문제

군나르는 웹사이트마다 다른 비밀번호를 쓴다. 전부 외우기는 어려워서, 사이트마다 비밀번호를 만든 방법만 기억해 둔다.

아주 중요한 어떤 사이트의 비밀번호는 음이 아닌 정수가 길게 나열된 파일에서 만들었다. 군나르는 xor 연산 $\oplus$ 를 좋아해서, 파일에 적힌 수 가운데 몇 개를 골라 xor 한 값을 비밀번호로 삼았다. 비트 하나에 대한 xor 는 $0 \oplus 0 = 1 \oplus 1 = 0$ , $0 \oplus 1 = 1 \oplus 0 = 1$ 로 정의된다. 정수 두 개의 xor 는 두 수를 이진법으로 적고 같은 자리의 비트끼리 xor 한 결과다. 예를 들어 $12 = (1100)_2$ 와 $5 = (101)_2$ 의 xor 는 $9 = (1001)_2$ 이다. 여러 수를 더하는 대신 xor 로 묶은 값을 xor 합이라고 부른다.

군나르는 xor 합이 가장 큰 부분집합을 골랐고, 그 xor 합이 비밀번호가 되었다. 고른 부분집합은 비어 있지 않다. 지금은 그런 부분집합을 찾는 방법을 잊어버려서 도움을 청하고 있다. 어느 사이트의 비밀번호인지는 알려 주지 않는다.

입력

첫째 줄에 파일에 적힌 수의 개수 $n$ 이 주어진다 ( $1 \le n \le 100\,000$ ).

둘째 줄에 공백으로 구분된 정수 $a_1, a_2, \dots, a_n$ 이 주어진다 ( $1 \le a_i \le 10^{18}$ ).

출력

비어 있지 않은 부분집합을 하나 골라 xor 합을 계산했을 때 얻을 수 있는 가장 큰 값을 한 줄에 출력한다.

예제3

예제 1
입력
```
3
1 3 5
```
예상 출력
```
7
```
예제 2
입력
```
4
2 6 4 8
```
예상 출력
```
14
```
예제 3
입력
```
1
1
```
예상 출력
```
1
```