Erdős-Szekeres (Large)

$X$는 $1$부터 $N$까지의 수를 한 번씩 사용해 나열한 수열이다. $X$에서 순서를 유지한 채 몇 개를 고른 것이 왼쪽에서 오른쪽으로 커지면 증가 부분수열, 작아지면 감소 부분수열이다. 예를 들어 $(5, 7, 8)$은 $(4, 5, 3, 7, 6, 2, 8, 1)$의 증가 부분수열이다.

폴 에르되시와 조지 세케레시는 약 80년 전에 이런 결과를 증명했다. 길이가 $N$인 어떤 $X$에도 길이가 $\sqrt{N}$ 이상인 증가 부분수열이나 길이가 $\sqrt{N}$ 이상인 감소 부분수열이 반드시 있다. 예를 들어 $(4, 5, 3, 7, 6, 2, 8, 1)$에는 길이가 4인 감소 부분수열 $(5, 3, 2, 1)$이 있다.

조합론 수업에서 이 정리를 예로 설명하려고 각 $i$마다 두 값을 계산했다.

• $A[i]$: $X[i]$를 가장 큰 원소로 하는 가장 긴 증가 부분수열의 길이, 즉 $X[i]$에서 끝나는 증가 부분수열의 최대 길이.
• $B[i]$: $X[i]$를 가장 큰 원소로 하는 가장 긴 감소 부분수열의 길이, 즉 $X[i]$에서 시작하는 감소 부분수열의 최대 길이.

증명의 핵심은 쌍 $(A[i], B[i])$가 모든 $i$에서 서로 다르다는 점이고, 여기서 어떤 $i$의 $A[i]$나 $B[i]$가 $\sqrt{N}$ 이상이라는 결론이 나온다. 위 수열의 두 값은 다음과 같다.

그런데 $A$와 $B$만 남고 원래 수열 $X$는 잊어버렸다. $A[i]$와 $B[i]$가 주어질 때 $X$를 복원하라.

$X$는 $1$부터 $N$까지의 수를 어떤 순서로 나열한 수열이다. 조건을 만족하는 $X$가 여러 개면 사전순으로 가장 작은 것을 출력한다. 사전순으로 가장 작다는 것은 $X[0]$이 가능한 한 작고, 그래도 여러 개가 남으면 $X[1]$이 가능한 한 작고, 이런 식으로 계속 이어진다는 뜻이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 각각 세 줄로 주어진다.

각 테스트 케이스의 첫 줄에 정수 $N$이 주어진다. 둘째 줄에는 $A[0], A[1], \dots, A[N-1]$이 공백으로 구분된 양의 정수 $N$개로 주어진다. 셋째 줄에는 $B[0], B[1], \dots, B[N-1]$이 같은 형식으로 주어진다.

제한

• $1 \le T \le 30$
• $1 \le N \le 2000$
• 각 테스트 케이스에는 조건을 만족하는 $X$가 적어도 하나 있다.

각 테스트 케이스마다 한 줄에 Case #x: 를 출력한 뒤 $X[0], X[1], \dots, X[N-1]$을 순서대로 공백으로 구분해 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다.