Given a list X, consisting of the numbers (1, 2, ..., N), an increasing subsequence is a subset of these numbers which appears in increasing order, and a decreasing subsequence is a subset of those numbers which appears in decreasing order. For example, (5, 7, 8) is an increasing subsequence of (4, 5, 3, 7, 6, 2, 8, 1).
Nearly 80 years ago, two mathematicians, Paul Erdős and George Szekeres proved a famous result: X is guaranteed to have either an increasing subsequence of length at least sqrt(N) or a decreasing subsequence of length of at least sqrt(N). For example, (4, 5, 3, 7, 6, 2, 8, 1) has a decreasing subsequence of length 4: (5, 3, 2, 1).
I am teaching a combinatorics class, and I want to "prove" this theorem to my class by example. For every number X[i] in the sequence, I will calculate two values:
i  X[i]  A[i]  B[i] +++ 0  4  1  4 1  5  2  4 2  3  1  3 3  7  3  4 4  6  3  3 5  2  1  2 6  8  4  2 7  1  1  1
I came up with a really interesting sequence to demonstrate this fact with, and I calculated A[i] and B[i] for every i, but then I forgot what my original sequence was. Given A[i] and B[i], can you help me reconstruct X?
X should consist of the numbers (1, 2, ..., N) in some order, and if there are multiple sequences possible, you should choose the one that is lexicographically smallest. This means that X[0] should be as small as possible, and if there are still multiple solutions, then X[1] should be as small as possible, and so on.
The first line of the input gives the number of test cases, T. T test cases follow, each consisting of three lines.
The first line of each test case contains a single integer N. The second line contains N positive integers separated by spaces, representing A[0], A[1], ..., A[N1]. The third line also contains N positive integers separated by spaces, representing B[0], B[1], ..., B[N1].
For each test case, output one line containing "Case #x: ", followed by X[0], X[1], ... X[N1] in order, and separated by spaces.
1 ≤ T ≤ 30.
It is guaranteed that there is at least one possible solution for X.
1 ≤ N ≤ 20.
1 ≤ N ≤ 2000.
Input 
Output 
2

Case #1: 1

Points  Correct  Attempted 

9pt  365  791 
15pt  182  271 