Problem Description

“But there’s nothing I wouldn’t do to wake up and remember it.”

Jonathan is fan of string problems. He is learning lexicographic order and suffix array these days.

String x is lexicographically less than string y, if either x is a prefix of y (and x $\neq$ y), or there exists such i (1 ≤ i ≤ min(|x|,|y|)), that $x_i < y_i$, and for any j (1 ≤ j < i), $x_j = y_j$. Here |a| denotes the length of the string a. The lexicographic comparison of strings is implemented by operator < in modern programming languages. For example, everybody is lexicographically smaller than somebody.

Let suf i be $x_ix_{i+1}\cdots x_n$ for string x of length n. In suffix array problems, there are two commonly used arrays: sa of length n and height of length n-1. Formally, $sa_i$ (1 ≤ i ≤ n) is the starting position of the i-th lexicographically smallest suffix sufj, which means $sa_i$ = j. And $height_i$ (2 ≤ i ≤ n) is the length of longest common prefix between suf $sa_{i-1}$ and suf $sa_i$. For example, the sa and height for remember is {6,4,2,7,5,3,8,1} and {0,2,1,0,1,0,1} respectively.

As we all know, Little Y is a Riddler. One day, Little Y got a string S of length n consisting of only lowercase letters. He used suffix-array algorithms to get the array sa and height. He erased several numbers in height and gave the two modified array to Jonathan.

Curiously, Jonathan wants to know what the string S is. Please help him to figure out a possible answer. Since there may be multiple answers, you only need to print the lexicographically smallest one. It is guaranteed that the answer exists.

Input

The first line contains one integer T (1 ≤ T ≤ 15) denoting the count of testcase.

For each test case,

The first line contains one integer n (1 ≤ n ≤ 5000), indicating the length of the string S.

The second line contains n integers $a_1,a_2,\cdots ,a_n$, indicating the array sa.

The third line contains n-1 integers $b_2,b_3,\cdots ,b_n$, indicating the modified array height. $b_i$ = -1 means that heighti is erased by Little Y. Otherwise, $height_i = b_i$.

It is guaranteed that $\sum n ≤ 4.1\times 10^4$.

Output

For each testcase, one line with one string S of length n, indicating the lexicographically smallest answer.

3
4
4 1 2 3
1 0 0
4
4 1 2 3
1 -1 0
11
11 4 8 1 5 9 2 6 10 3 7
-1 -1 -1 0 -1 -1 -1 0 -1 3

abca
aaba
abcabbcabca