34189번 - 두 수열 만들기 스페셜 저지

$2N$개의 정수 $x_1, x_2, \cdots, x_{2N}$이 주어진다.

다음 조건을 만족하며, $x_1, x_2, \cdots, x_{2N}$에서 중복없이 각각 $N$개를 사용하여 만들 수 있는 수열 $A = A_1, A_2, \cdots, A_N$과 수열 $B = B_1, B_2, \dots, B_N$을 출력하시오.

• 임의의 $A_i$에 대해 $A_i \oplus x = 2^j \ (j$는 음이 아닌 정수$)$를 만족하는 $x$가 수열 $B$에 없어야 한다.
• 임의의 $B_i$에 대해 $B_i \oplus x = 2^j \ (j$는 음이 아닌 정수$)$를 만족하는 $x$가 수열 $A$에 없어야 한다.

첫째 줄에 $N$이 주어진다. $(1 \leq N \leq 2\,000)$

둘째 줄에 $x_1, x_2, \cdots, x_{2N}$이 공백으로 구분되어 주어진다. $(0 \leq x_i < 2^{20})$

입력으로 주어지는 모든 $x_i$는 서로 다르다.

첫째 줄에 $A_1, A_2, \cdots, A_N$을 공백으로 구분하여 출력한다.

둘째 줄에 $B_1, B_2, \cdots, B_N$을 공백으로 구분하여 출력한다.

수열을 출력할 때 출력하는 순서는 상관없다.

만약 수열을 만들 수 있는 경우가 여러 가지라면 그중 아무거나 출력하고, 수열을 만들 수 없는 경우에는 -1을 대신 출력한다.

$\oplus$은 Bitwise XOR을 뜻하며, 음이 아닌 두 정수 $A, B$의 $A \oplus B$는 다음과 같이 정의된다.

• 이진법으로 생각했을 때, $A$의 $2^k$의 자릿수와 $B$의 $2^k$의 자릿수가 서로 다르면 $A \oplus B$의 $2^k$의 자릿수가 $1$이고, 같으면 $A \oplus B$의 $2^k$의 자릿수가 $0$이다. (단, $k \geq 0$)
• 예를 들어 $12 \oplus 10$은 $12 = 1100_{(2)}, 10 = 1010_{(2)}$이므로 $1100_{(2)} \oplus 1010_{(2)} = 0110_{(2)} = 6$이다.