Merge Not Sort

당신은 병합 정렬(Merge Sort) 알고리즘을 연구하고 있다. 병합 정렬은 분할 정복 원리를 바탕으로 한 정렬 알고리즘이다. 배열을 길이가 같은 두 부분 배열로 나누고, 각각을 정렬한 뒤 정렬된 두 부분 배열을 합쳐 최종적으로 정렬된 배열을 만든다.

특히 병합 과정에 관심이 있다. 흔히 쓰는 병합 구현은 두 부분 배열의 첫 원소를 반복해서 비교하고, 더 작은 원소를 새 배열로 옮긴다. 병합 알고리즘은 다음 의사 코드로 나타낼 수 있다.

Merge(A[1..N], B[1..N]):
    C = []
    i = 1
    j = 1
    while i ≤ N AND j ≤ N:
        if A[i] < B[j]:
            append A[i] to C
            i = i + 1
        else:
            append B[j] to C
            j = j + 1
    while i ≤ N:
        append A[i] to C
        i = i + 1
    while j ≤ N:
        append B[j] to C
        j = j + 1
    return C

배열 A와 B가 정렬되어 있지 않을 때 병합 알고리즘이 어떻게 동작하는지 알고 싶다. 예를 들어 $A = [3, 1, 6]$, $B = [4, 5, 2]$이면 $\text{Merge}(A, B) = [3, 1, 4, 5, 2, 6]$이다.

병합 알고리즘의 동작을 더 깊이 이해하기 위해 다음 문제를 풀어 보자. 길이가 $2 \cdot N$인 배열 $C$가 주어지며, $C$는 $1$부터 $2 \cdot N$까지의 수를 한 번씩 포함하는 순열이다. 길이가 각각 $N$인 배열 $A$와 $B$를 만들어 $\text{Merge}(A, B) = C$가 되게 하거나, 그것이 불가능한지 판단하라.

첫째 줄에 정수 $N$ ($1 ≤ N ≤ 1000$)이 주어진다.

둘째 줄에 $2 \cdot N$개의 정수 $C_i$가 주어진다. 배열 $C$는 $1$부터 $2 \cdot N$까지의 수를 한 번씩 포함하는 순열이다.

$\text{Merge}(A, B) = C$를 만족하는 길이 $N$의 배열 $A$와 $B$를 만들 수 없으면 -1을 출력한다. 그렇지 않으면 첫째 줄에 $A_i$를 $N$개, 둘째 줄에 $B_i$를 $N$개 출력한다. 가능한 답이 여러 개이면 그중 하나를 출력한다.