순열 구하기

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

1. 두 배열의 길이가 같다면 다음과 같이 연산한다.

$A \oplus B = \[ A\_{1} \oplus B\_{1}, A\_{2} \oplus B\_{2}, \cdots , A\_{N-1} \oplus B\_{N-1}, A\_{N} \oplus B\_{N} ]$

2. 길이가 $N$인 배열 $A$와 길이가 $M$인 배열 $B$가 있는 경우 다음과 같이 연산한다. ( $N < M$ )

$A \oplus B = \[ A\_{1} \oplus B\_{1}, A\_{2} \oplus B\_{2}, \cdots , A\_{N-1} \oplus B\_{N-1}, A\_{N} \oplus B\_{N}, B\_{N+1} , \cdots , B\_{M-1}, B\_{M} ]$

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

여기서 $\oplus$는 bitwise xor 연산을 의미한다. bitwise xor 연산의 정의는 하단 힌트 탭에 있다.

첫째 줄에 순열의 길이 $N$이 주어진다. $\left( 1 \leq N \leq 5\\,000 \right)$

둘째 줄에 배열의 원소 $B\_{i}$가 공백으로 구분되어 주어진다.

순열 $P$로 복원할 수 있는 배열 $B$만 주어지며 $B\_{i}$는 항상 $2^{31}$보다 작은 음이 아닌 정수다.

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

bitwise xor 연산은 두 개의 2진수 값에 대해 자리 단위로 적용되는 연산이다. 먼저 피연산자로 주어진 두 값을 2진수로 표현한다. 그 뒤에 두 값의 각 자릿수를 비교해, 두 값이 다르면 1, 두 값이 같으면 0으로 계산한다.

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