Atlansert stumbled upon a crack, and the Z-shaped pipe cat said that stories might be hidden there.

Given a positive integer $n$ and two permutations $r$ and $c$ of length $n$, find a matrix that satisfies all of the following conditions:

• The matrix has $n$ rows and $n$ columns, and all elements are integers in the range $[0, n]$.
• The MEX value of the elements in the $i$-th row is $r_i$.
• The MEX value of the elements in the $i$-th column is $c_i$.

It can be proven that such a matrix always exists.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$, where the order of these integers can be arbitrary. For example, $[2, 3, 1, 5, 4]$ is a permutation, but $[1, 2, 2]$ is not (because $2$ appears twice), and $[1, 3, 4]$ is not (because $n=3$ but the array contains $4$).

The MEX (Minimum Excluded) of a set of integers $a_1, a_2, \dots, a_k$ is the smallest non-negative integer $x$ that does not appear in the set. For example, $\text{MEX}([2, 2, 1]) = 0$ (because $0$ is not in the array), $\text{MEX}([3, 1, 0, 1]) = 2$ (because $0$ and $1$ are in the array, but $2$ is not), and $\text{MEX}([0, 3, 1, 2]) = 4$ (because $0, 1, 2,$ and $3$ are in the array, but $4$ is not).

Input

Each test case contains multiple test data. The first line contains an integer $T$ ($1 \le T \le 10^3$), representing the number of test cases.

For each test case: The first line contains a positive integer $n$ ($1 \le n \le 2 \times 10^3$). The second line contains a permutation $r_1, r_2, \dots, r_n$ of length $n$. The third line contains a permutation $c_1, c_2, \dots, c_n$ of length $n$.

It is guaranteed that the sum of $n$ over all test cases in each test point does not exceed $2 \times 10^3$.

Output

For each test case, output $n$ lines, each containing $n$ integers, representing a matrix that satisfies all the conditions of the problem. If there are multiple such matrices, output any one of them.

Examples

Input 1

2
4
2 1 3 4
3 4 1 2
5
2 1 4 3 5
1 4 2 5 3

Output 1

0 0 4 1
2 3 4 0
1 2 0 1
0 1 2 3
0 0 0 0 1
0 0 0 2 0
2 3 3 1 0
2 1 0 4 2
0 2 1 3 4

Note

The input and output volume for this problem is large; please be mindful of the input/output methods used.