L. Leak
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Atlansert encountered a leak, and the Z-tube Cat said there were stories hidden there.

Given a positive integer $$$n$$$ and two permutations $$$^{\text{*}}$$$ $$$r,c$$$ of length $$$n$$$.

Find a matrix satisfying all the following conditions:

  • The matrix has $$$n$$$ rows and $$$n$$$ columns, with all elements being integers in the range $$$[0,n]$$$.
  • The MEX$$$^{\text{†}}$$$ value of the element in the $$$i$$$th row is $$$r_i$$$.
  • The MEX value of the $$$i$$$th column element is $$$c_i$$$.

It can be proved that such a matrix exists.

$$$^{\text{*}}$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in an arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation of length 5, but $$$[1,2,2]$$$ is not a permutation($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation($$$n=3$$$ but there is $$$4$$$ in the array).

$$$^{\text{†}}$$$ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

  • The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array.
  • The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not.
  • The MEX of $$$[0,3,1,2]$$$ is $$$4$$$, because $$$0$$$, $$$1$$$, $$$2$$$ and $$$3$$$ belong to the array, but $$$4$$$ does not.
Input

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

For each test case:

The first line gives a positive integer $$$n(1\le n\le2\times 10^3)$$$.

The second line provides a permutation of length $$$n$$$: $$$r_1, r_2, \ldots, r_n$$$.

The third line provides another permutation of length $$$n$$$: $$$c_1, c_2, \ldots, c_n$$$.

It is guaranteed that the sum of all $$$n$$$ values across all test cases 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 conditions of this problem. If multiple such matrices exist, output any one of them.

Example
Input
2
4
2 1 3 4 
3 4 1 2 
5
2 1 4 3 5 
1 4 2 5 3
Output
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