I. The Paintress
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have $$$n$$$ boards and $$$n$$$ paint colors. The $$$i$$$-th board has length $$$l_i$$$, and there are $$$c_j$$$ units of paint of color $$$j$$$.

The total length of all boards equals the total amount of paint: $$$\sum_{i=1}^{n} l_i = \sum_{j=1}^{n} c_j.$$$

You must use all the paint and fully cover every board. Formally, construct a matrix $$$x$$$ of size $$$n \times n$$$, where $$$x_{i,j}$$$ is a non-negative integer equal to the number of units of board $$$i$$$ painted with color $$$j$$$. It must satisfy $$$\sum_{j=1}^{n} x_{i,j} = l_i$$$ for every board $$$i$$$, and $$$\sum_{i=1}^{n} x_{i,j} = c_j$$$ for every color $$$j$$$.

A painting is called simple if the boards can be ordered as $$$p_1, p_2, \ldots, p_n$$$ so that, for every $$$k$$$ from $$$1$$$ to $$$n$$$, the first $$$k$$$ boards $$$p_1, p_2, \ldots, p_k$$$ use at most $$$k$$$ distinct colors in total — that is, the number of colors appearing on at least one of these $$$k$$$ boards is at most $$$k$$$.

It can be shown that a simple painting always exists. You must output a simple painting together with such an order as proof that it is simple.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of boards and colors.

The second line contains $$$n$$$ integers $$$l_1, l_2, \ldots, l_n$$$ ($$$1 \le l_i \le 10^9$$$) — the lengths of the boards.

The third line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_j \le 10^9$$$) — the amounts of each color of paint.

It is guaranteed that $$$\sum_{i=1}^{n} l_i = \sum_{j=1}^{n} c_j$$$, and that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output

For each test case, output $$$n + 1$$$ lines.

The first $$$n$$$ lines describe the painting: the $$$i$$$-th of them contains $$$n$$$ non-negative integers $$$x_{i,1}, x_{i,2}, \ldots, x_{i,n}$$$.

The last line contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ — a permutation of $$$1, 2, \ldots, n$$$ — such that for every $$$k$$$ from $$$1$$$ to $$$n$$$, boards $$$p_1, \ldots, p_k$$$ use at most $$$k$$$ distinct colors in total.

If there are multiple valid answers, output any of them.

Example
Input
1
3
5 2 3
2 5 3
Output
0 2 3
2 0 0
0 3 0
3 1 2
Note

In the first test case, one valid painting is shown below, with the board lengths $$$l_i$$$ in the right margin and the paint amounts $$$c_j$$$ along the bottom:

color $$$1$$$color $$$2$$$color $$$3$$$$$$l_i$$$
board $$$1$$$$$$0$$$$$$2$$$$$$3$$$$$$5$$$
board $$$2$$$$$$2$$$$$$0$$$$$$0$$$$$$2$$$
board $$$3$$$$$$0$$$$$$3$$$$$$0$$$$$$3$$$
$$$c_j$$$$$$2$$$$$$5$$$$$$3$$$

Every row sum equals the board's length $$$l_i$$$ and every column sum equals the paint amount $$$c_j$$$, so the painting is valid.

The order $$$p = [3, 1, 2]$$$ shows that the painting is simple. Add the boards one at a time in this order, keeping track of every color used so far:

  • Take board $$$3$$$ first: it uses only color $$$2$$$, so $$$1$$$ color has been used so far, and $$$1 \le 1$$$.
  • Add board $$$1$$$: it uses colors $$$2$$$ and $$$3$$$, so the colors used so far are $$$\{2, 3\}$$$ — $$$2$$$ colors, and $$$2 \le 2$$$.
  • Add board $$$2$$$: it uses color $$$1$$$, so the colors used so far are $$$\{1, 2, 3\}$$$ — $$$3$$$ colors, and $$$3 \le 3$$$.

At every step, the number of colors used so far is at most the number of boards taken so far, so the painting is simple.