E. Exam
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yessine was in the middle of an exam when he got bored. He doesn't really like exams or studying, but he likes problem-solving so he unconsciously started thinking about random problems. At that moment , one particular problem came to his mind:

You have to make an $$$n\times n$$$ grid consisting of white cells and black cells. There are only two constraints:

  1. The number of black cells on the $$$i^\texttt{th}$$$ column is $$$C_i$$$
  2. The number of black cells on the $$$i^\texttt{th}$$$ row is $$$R_i$$$

Yessine would've loved to solve this problem, but he remembered he was taking an exam and he must answer the questions or he would fail, so he left it to you.

Input

The first line contains one integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases.

The first line of each test case contains the integer $$$1\leq n \le 2000$$$

The second line of each test case contains $$$n$$$ space separated integers $$$0\leq C_1,\dots, C_n \leq n$$$

The third line of each test case contains $$$n$$$ space separated integers $$$0\leq R_1,\dots, R_n \leq n$$$

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$4$$$.$$$10^6$$$

Output

If there exists such $$$n\times n$$$ grid, output any (black cells are represented by 1 and white cells are represented by 0) else output $$$-1$$$

Example
Input
3
4
3 3 3 2
3 4 1 3
3
3 3 1
3 3 2
4
2 2 3 2
2 2 3 2
Output
0 1 1 1 
1 1 1 1 
1 0 0 0 
1 1 1 0 
-1
1 1 0 0 
0 0 1 1 
0 1 1 1 
1 0 1 0
Note

For the second test case, let's suppose that such $$$3\times 3$$$ matrix $$$A$$$ exists. As $$$R_1=R_2=C_1=C_2=3,$$$ necessarily, we have $$$A=\begin{matrix} 1&1&1\\ 1&1&1\\ 1&1& * \end{matrix}.$$$ This implies that $$$C_3\ge 2,$$$ which is a contradiction as $$$C_3=1.$$$

Therefore, such matrix does not exist.