시간 제한메모리 제한제출정답맞힌 사람정답 비율
2.5 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)2842187.692%

문제

AI Network에서 일하는 루노(Runo)들은 이진수를 사용하며, 이진수 표현에 $1$이 많은 수를 좋아한다.

루노들을 관리하는 아인(AIN)이는 루노들의 동기 부여를 위해 앞으로 $N$일간 날마다 가장 열심히 일한 루노에게 "오늘의 루노상"을 수여하려고 한다. 이 상의 상품은 루노들이 좋아할 법한 이진수 표현에 $1$이 많은 수이다.

어떤 수를 상품으로 줘야 할지 고민하던 아인이는 본인이 임의로 수를 선택하는 것은 참 힘든 일임을 깨닫고, 다음 $N$일 동안 매일 하나의 정수를 배달해 주는 서비스를 구독했다. 앞으로 $i$번째 날에 받을 수를 $V_i$라고 하자.

아인이는 매일 그날까지 모은 수들을 보고, 다음의 방식으로 루노들에게 줄 상품을 만든다.

  1. 오늘이 서비스를 구독한 $i$번째 날이라면, $V_1, V_2, \cdots, V_i$ 중에서 일부를 마음대로 고른다. 이때 수를 하나도 고르지 않거나, 전부 고를 수도 있다.
  2. 고른 수들을 전부 bitwise XOR한 결괏값을 계산한다. 수를 하나도 고르지 않았을 경우 결괏값은 $0$, 하나만 골랐을 경우 결괏값은 고른 수 그대로이다.

아인이는 이렇게 만들 수 있는 수 중에서 이진수 표현에 $1$이 가장 많은 수를 하나 선택해 상품으로 주려고 한다.

앞으로 $N$일간, 날마다 아인이가 상품으로 선택할 수 있는 수를 하나 구해 보자.

입력

첫 번째 줄에 아인이가 루노들에게 상을 주려는 일수이자 정수 배달 서비스를 구독하는 일수 $N$이 주어진다.

다음 $N$개의 줄에 서비스를 통해 배달받는 정수가 한 줄에 하나씩 주어진다. 이 중 $i$번째 줄에 주어지는 수는 $V_i$이다.

출력

$N$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 아인이가 $i$번째 날에 상품으로 선택할 수 있는 수를 하나 출력한다.

제한

  • $1 \leq N \leq 111$
  • $0 \leq V_i \leq 111\,111\,111\,111\,111$

예제 입력 1

2
3
5

예제 출력 1

3
6

첫 번째 날에는 $3$이 배달된다. 아인이는 수를 선택하지 않고 $0$을 만들거나 배달받은 $3$을 선택해서 $3$을 만들 수 있는데, $0$은 이진수로 표현해도 $0$이므로 $3$을 선택한다.

두 번째 날에는 $5$가 배달되고, 상품으로 줄 수 있는 새로운 후보로 $5$와 $6$($=3 \oplus 5$)이 생긴다. 이때 $3$, $5$, $6$이 모두 이진수로 표현할 때 $1$이 $2$개 등장하므로, 셋 중 어떤 것을 상품으로 선택해도 상관없다.

여기서 $\oplus$는 bitwise XOR 연산을 나타낸다.

예제 입력 2

3
6
14
9

예제 출력 2

6
14
15

첫 번째 날에는 $6$이 배달되고, 아인이는 위 예제의 첫 번째 날과 마찬가지로 배달받은 $6$을 선택해서 $6$을 만든다.

두 번째 날에는 $14$가 배달되고, 상품으로 줄 수 있는 새로운 후보로 $14$와 $8$($=6 \oplus 14$)이 생긴다. 네 가지 후보 중 $14$가 이진수로 표현할 때 $1$이 $3$개로 가장 많이 등장하므로, 아인이는 $14$를 상품으로 선택한다.

세 번째 날에는 $9$가 배달되고, 상품으로 줄 수 있는 새로운 후보로 $9$, $15$($=6 \oplus 9$), $7$($=14 \oplus 9$), $1$($=6 \oplus 14 \oplus 9$)이 생긴다. 아인이는 총 $8$가지의 후보 중 이진수로 표현할 때 $1$이 $4$개 등장하는 유일한 수인 $15$를 상품으로 선택한다.

예제 입력 3

3
1010000000
110
1

예제 출력 3

1010000000
1010000110
1010000111

출처

Contest > AI Network Scholarium > AI Network Scholarium I E번