순열 구하기

$1$부터 $N$까지의 정수로 이루어진 길이 $N$의 순열 $P$가 있다. 배열 $A_{i}$는 $P$의 처음 $i$($1 \le i \le N$)개 원소를 정렬한 길이 $i$의 배열이다. 배열 $B$는 $A_{1} \oplus A_{2} \oplus \cdots \oplus A_{N-1} \oplus A_{N} \oplus P$ 연산을 수행한 새로운 배열이다. 두 배열의 xor 연산은 다음 절차로 진행한다.

1. 두 배열의 길이가 같으면 같은 위치의 원소끼리 xor 한다. $A \oplus B = [A_{1} \oplus B_{1}, A_{2} \oplus B_{2}, \cdots, A_{N} \oplus B_{N}]$

2. 길이가 $N$인 배열 $A$와 길이가 $M$인 배열 $B$가 있고 $N < M$이면 다음과 같이 연산한다. $A \oplus B = [A_{1} \oplus B_{1}, \cdots, A_{N} \oplus B_{N}, B_{N+1}, \cdots, B_{M}]$

배열 $B$가 주어졌을 때 원래 순열 $P$를 구하는 프로그램을 작성하시오.

여기서 $\oplus$는 비트 단위 xor 연산을 뜻한다. 자세한 정의는 힌트에 있다.

첫째 줄에 순열의 길이 $N$이 주어진다. ($1 \le N \le 5000$)

둘째 줄에 배열의 원소 $B_{i}$가 공백으로 구분되어 주어진다. 순열 $P$로 복원할 수 있는 배열 $B$만 주어진다. $B_{i}$는 항상 $2^{31}$보다 작은 음이 아닌 정수다.

첫째 줄에 순열 $P$의 원소를 공백으로 구분해 출력한다.

비트 단위 xor 연산은 두 이진수 값을 자리마다 계산하는 연산이다. 먼저 두 값을 이진수로 나타낸다. 그다음 각 자릿수를 비교한다. 두 자릿수가 다르면 결과는 1이고, 같으면 0이다.

예를 들어 $12 \oplus 6$의 값은 $10$이다. $12$는 이진수로 $1100_{(2)}$이고, $6$은 $0110_{(2)}$이다. 계산 과정은 아래 그림과 같다. 결과는 $1010_{(2)}$, 즉 $10$이다.