XOR 합 2

시간 제한2초메모리 제한512 MB

요약

10^18 이하의 수 100,000개로 이루어진 수열에서 부분수열을 골라 그 원소들의 XOR 값이 최대가 되도록 한다.

문제

$N$ 개의 수로 이루어진 수열 $A$ 가 주어진다.

수열 $A$ 에서 부분 수열을 하나 고르려고 한다. 부분 수열의 XOR 합은 부분 수열에 들어 있는 모든 원소를 XOR한 값이다.

수열 $A$ 가 주어졌을 때 XOR 합이 가장 큰 부분 수열을 찾는 프로그램을 작성하시오.

첫째 줄에 수열의 크기 $N$ ( $1 \le N \le 100{,}000$ )이 주어진다. 둘째 줄에는 수열 $A$ 에 들어 있는 수 $N$ 개가 주어진다. 수열 $A$ 에 들어 있는 수는 $10^{18}$ 보다 작거나 같은 자연수이다.

수열 $A$ 의 부분 수열 중 XOR 합이 가장 큰 부분 수열의 XOR 합을 출력한다.