C. Reordering Red Pandas
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Eric's $$$n$$$ red pandas have been mixed up!

They currently lie on the number line, occupying points $$$p_1, p_2, \dots p_n$$$. You are given the distance between all pairs of red pandas. Please help Eric figure out the order of the pandas.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 500)$$$, the number of test cases.

The first line of each test case contains an integer, $$$n$$$ $$$(1 \leq n \leq 1000)$$$.

Then the line after that contains $$$n$$$ integers, $$$p_1, p_2, \dots p_n$$$ $$$(1 \leq p_i \leq 10^9)$$$, given in increasing order.

Then $$$n$$$ lines follow. The $$$i$$$th of these lines will contain $$$n$$$ integers, $$$d_{i1}, d_{i2}, \dots d_{in}$$$, where $$$d_{ij}$$$ is the distance between red panda $$$i$$$ and red panda $$$j$$$. Note that a panda is distance $$$0$$$ from itself.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output

For each test case, output one line containing $$$n$$$ integers, $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ is the panda at point $$$p_i$$$. If there are multiple correct answers, output any.

Example
Input
2
3
1 2 3
0 1 2
1 0 1
2 1 0
4
1 3 8 9
0 6 2 5
6 0 8 1
2 8 0 7
5 1 7 0
Output
3 2 1 
3 1 4 2
Note

For the first test case, both $$$[1, 2, 3]$$$ and $$$[3, 2, 1]$$$ are valid answers.

Problem Credits: Mythreya Dharani