집합과 쿼리

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

요약

집합에 대한 삽입과 삭제가 최대 50만 번 주어질 때, 매 질의 후 집합의 부분집합으로 만들 수 있는 최대 XOR 값을 출력한다.

문제

집합 $S$ 에 다음과 같은 쿼리를 수행해야 한다.

각 쿼리를 수행할 때마다, 집합에 포함된 모든 값을 XOR한 결과가 가장 큰 $S$ 의 부분 집합 $T$ 를 찾아야 한다.

첫째 줄에 쿼리의 개수 $N$ ( $1 \le N \le 500{,}000$ )이 주어진다. 둘째 줄부터 $N$ 개의 줄에 쿼리가 한 줄에 하나씩 주어진다. 집합에 추가되는 수는 $2{,}000{,}000{,}000$ 보다 작거나 같은 자연수이다.

집합에 이미 들어있는 수를 추가하는 쿼리와 집합에 없는 수를 제거하는 쿼리는 주어지지 않는다.

각 쿼리를 수행한 후에 $T$ 에 포함된 모든 값을 XOR한 결과를 출력한다. 쿼리를 수행한 후에 집합 $S$ 의 크기가 $0$ 인 경우에는 $0$ 을 출력한다.