시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 59 35 10 33.333%

문제

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

  • x: 집합 S에 x를 추가한다.
  • -x: 집합 S에서 x를 제거한다.

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

입력

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

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

출력

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

예제 입력 1

6
1
2
3
4
-2
-3

예제 출력 1

1
3
3
7
7
5

예제 입력 2

5
1
-1
2
-2
3

예제 출력 2

1
0
2
0
3

출처