The annual variety show "New Code of China" has begun again. Zayid has dreamed of becoming a programmer since he was a child, and he felt this was a stage to showcase himself, so he signed up without hesitation.

Zayid passed the auditions with ease. The next stage is the mentor blind selection, and the rules for this stage are as follows:

There are a total of $n$ contestants (numbered from 1 to $n$), each of whom writes a piece of code and introduces their dream. Then, all mentors rank these contestants. To avoid subsequent trouble, it is stipulated that there are no ties in the rankings.

At the same time, each contestant independently fills out a preference form to evaluate a total of $m$ mentors (numbered from 1 to $m$). The preference form contains $m$ levels of preferences. For each level of preference, a contestant is allowed to fill in at most $C$ mentors, and each mentor can be filled in at most once by each contestant (giving up on certain mentors is also allowed).

After both parties have completed their work, the admission process begins. Each mentor has an upper limit on the number of people in their team, which means that some contestants' higher preferences, or even all of their preferences, may not be satisfied.

The program team defines "the admission result for the top $i$ is optimal" as follows: The admission result for the top 1 is optimal if and only if the 1st-ranked contestant is admitted by their highest non-empty preference (in particular, if the 1st-ranked contestant did not fill out a preference form, then that contestant is eliminated). The admission result for the top $i$ is optimal if and only if, given that the admission result for the top $i-1$ is optimal, the $i$-th ranked contestant is admitted by their theoretically highest possible preference (in particular, if the $i$-th ranked contestant did not fill out a preference form, or if the teams of all mentors in their preferences are already full, then that contestant is eliminated).

If a scheme satisfies "the admission result for the top $n$ is optimal," we can simply call this scheme optimal.

For example, suppose there are 2 mentors, Teacher T and Teacher F, each with a team capacity of 1; and 2 contestants, Zayid and DuckD, ranked 1st and 2nd respectively. The following 3 preference forms and their corresponding optimal admission results are shown in the tables:

It can be proven that for the preference forms above, the corresponding schemes are the unique optimal admission results.

Everyone has their own ideal value $s_i$, which indicates that the $i$-th student hopes to be admitted by their $s_i$-th or higher preference; if not, they will be very frustrated.

Now, all contestants' preference forms and rankings have been made public. Coincidentally, each contestant's rank is exactly the same as their ID.

For every contestant, Zayid wants to know the answers to the following two questions: In the optimal admission scheme, which preference rank will they be admitted by? Assuming other contestants' relative rankings remain unchanged, how many places must they rise at least to ensure they are not frustrated?

As a talented coder on "New Code of China," Zayid naturally solved this problem easily. However, he still wants you to calculate it again to verify the correctness of his calculations.

Input

Read the data from the file mentor.in.

Each test point contains multiple test cases. The first line contains 2 non-negative integers $T$ and $C$, representing the number of test cases and the maximum number of mentors allowed per preference level, respectively.

The following lines describe each test case. For each test case: The first line contains two positive integers $n, m$. $n, m$ represent the number of contestants and the number of mentors, respectively. The second line contains $m$ space-separated positive integers: the $i$-th integer is $b_i$. $b_i$ represents the upper limit of the number of people in the team of the mentor with ID $i$. From the 3rd line to the $n+2$-th line, each line contains $m$ space-separated non-negative integers: the $j$-th number in the $i+2$-th line is $a_{i,j}$. $a_{i,j}$ indicates that the contestant with ID $i$ has placed the mentor with ID $j$ in their $a_{i,j}$-th preference. In particular, if $a_{i,j} = 0$, it means the contestant did not include this mentor in their preference form. In this part, it is guaranteed that no positive number appears more than $C$ times in each row (0 may appear more than $C$ times), and it is guaranteed that all $a_{i,j} \le m$. The $n+3$-th line contains $n$ space-separated positive integers, where the $i$-th integer is $s_i$. $s_i$ represents the ideal value of the contestant with ID $i$. In this part, it is guaranteed that $s_i \le m$.

Output

Output to the file mentor.out.

Output the answers for each test case in order. For each test case, output 2 lines: The first line outputs $n$ space-separated positive integers, where the $i$-th integer means: In the optimal admission scheme, the contestant with ID $i$ is admitted by this preference level. In particular, if the contestant is eliminated, this number is $m+1$. The second line outputs $n$ space-separated non-negative integers, where the $i$-th integer means: The minimum number of places the contestant with ID $i$ needs to rise to not be frustrated. In particular, if the contestant will definitely be frustrated, this number is $i$.

Examples

Input 1

3 5
2 2
1 1
2 2
1 2
1 1
2 2
1 1
1 2
1 2
2 1
2 2
1 1
0 1
0 1
2 2

Output 1

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

Note 1

The three sets of data correspond to the three tables in the Description. For the first set of data: Since contestant 1 did not fill in a first preference, they cannot be admitted by their first preference and will definitely be frustrated. Contestant 2 is not frustrated based on their original ranking, so they do not need to improve their ranking. For the second and third sets of data: Contestant 1 does not need to improve their ranking. Contestant 2, who hopes to be admitted by their first preference, must rise to 1st place to get their wish.

Input 2

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

Output 2

1 1 3 2
0 0 0 0

Note 2

Contestant 1's first preference only included mentor 2, so contestant 1 must be admitted by mentor 2. Contestant 2's first preference only included mentor 3, so contestant 2 must be admitted by mentor 3. Since the teams for mentors 2 and 3 are both full, and both contestants 3 and 4 filled in mentor 1, they will both be admitted by mentor 1. Therefore, contestants 1 and 2 are both admitted by their 1st preference, contestant 3 is admitted by their 3rd preference, and contestant 4 is admitted by their 2nd preference. Since they all got their wishes, they do not need to improve their rankings.

Subtasks

For all test cases, it is guaranteed that $T \le 5$. For all data in all test cases, it is guaranteed that $m \le n \le 200$ and $b_i \le n$.