Background

The annual variety show "China's New Code" has started again. Zayid has always dreamed of becoming a programmer, and he sees this as a stage to showcase himself, so he didn't hesitate to sign up.

Problem Description

Zayid smoothly passed the preliminary selection. The next stage is the blind selection by mentors. The rules for this phase are as follows:

A total of $n$ contestants (numbered from $1$ to $n$) each write a piece of code and introduce their dreams. Then, all mentors rank these contestants. To avoid subsequent complications, it is stipulated that there are no ties in the rankings.

Each contestant will independently fill out a wish list to evaluate a total of $m$ mentors (numbered from $1$ to $m$). The wish list contains a total of $m$ levels of wishes. For each level of wish, contestants are allowed to list up to $C$ mentors, and each mentor can be listed by each contestant only once (it is also allowed to omit some mentors).

After both parties have completed their work, the admission process begins. Each mentor has a limit on the number of team members, which means that some contestants' higher wishes, or even all their wishes, may not be fulfilled. The show defines "the optimal admission result for the top $i$ contestants" as follows:

• The optimal admission result for the top $1$ contestant is if and only if the first contestant is admitted by their highest non-empty wish (specifically, if the first contestant did not fill out a wish list, then this contestant is eliminated).

• The optimal admission result for the top $i$ contestants is when, under the condition that the admission result for the top $i-1$ contestants is optimal, the $i$-th contestant is admitted by their theoretically possible highest wish (specifically, if the $i$-th contestant did not fill out a wish list, or all mentors in their wishes are full, then this contestant is eliminated).

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

For example, there are $2$ mentors, Teacher T and Teacher F, each with a team size limit of $1$ person; Zayid and DuckD are ranked $1$st and $2$nd respectively. The following $3$ wish lists and their corresponding optimal admission results are shown in the table:

It can be proven that for the above wish lists, the corresponding plans are the only optimal admission results.

Each person has their own ideal value $s_i$, which means the $i$-th contestant hopes to be admitted by the $s_i$-th or higher wish. If not, they will be very disappointed.

Now, all contestants' wish lists and rankings have been published. Coincidentally, each contestant's ranking is exactly the same as their number.

For each contestant, Zayid wants to know the answers to the following two questions:

• In the optimal admission plan, which wish will he be admitted by.

• Given the relative rankings of other contestants remain unchanged, at least how many places does he need to move up to avoid disappointment.

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

Input Format

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

Next, each set of data is described in order. For each set of data:

• The first line contains $2$ space-separated 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 team size limit for the mentor numbered $i$.

• From the third line to the $(n + 2)$-th line, each line contains $m$ space-separated non-negative integers: the $(i + 2)$-th line, the $j$-th number from the left is $a_{i,j}$.

$a_{i,j}$ represents that the contestant numbered $i$ has placed the mentor numbered $j$ in the $a_{i,j}$-th wish. Specifically, if $a_{i,j} = 0$, it means that the contestant did not include this mentor in the wish list.

In this part, it is guaranteed that no positive number appears more than $C$ times in a row ($0$ may appear more than $C$ times), and it is guaranteed that all $a_{i,j} \leq 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 for the contestant numbered $i$.

In this part, it is guaranteed that $s_i \leq m$.

Output Format

Output the answers for each set of data in order. For each set of data, output $2$ lines:

• The first line contains $n$ space-separated positive integers, where the $i$-th integer represents:

In the optimal admission plan, the wish level by which the contestant numbered $i$ will be admitted.

Specifically, if the contestant is eliminated, this number is $m + 1$.

• The second line contains $n$ space-separated non-negative integers, where the $i$-th integer represents:

The minimum number of places the contestant numbered $i$ needs to move up to avoid disappointment.

Specifically, if the contestant will definitely be disappointed, this number is $i$.

Sample Input and Output

Input Sample #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 Sample #1

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

Input Sample #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 Sample #2

1 1 3 2
0 0 0 0

Notes/Hints

• Sample $1$ Explanation

The three sets of data correspond to the three tables in the Problem Description.

For the first set of data: Since contestant $1$ did not fill out the first wish, he is definitely unable to be admitted by the first wish and will certainly be disappointed. Contestant $2$ is not disappointed with the original ranking, so he does not need to improve his ranking.

For the second and third sets of data: Contestant $1$ does not need to improve his ranking. Contestant $2$, who hopes to be admitted by the first wish, must move up to the first place to achieve his goal.

• Sample $2$ Explanation

Contestant $1$'s first wish only lists mentor $2$, so contestant $1$ will definitely be admitted by mentor $2$.

Contestant $2$'s first wish only lists mentor $3$, so contestant $2$ will definitely be admitted by mentor $3$.

Since both mentors $2$ and $3$ are full, and contestants $3$ and $4$ both listed mentor $1$, they will both be admitted by mentor $1$.

So contestants $1$ and $2$ are both admitted by their first wish, contestant $3$ is admitted by his third wish, and contestant $4$ is admitted by his second wish.

Since they all achieved their wishes, they do not need to improve their rankings.

• For all test points, it is guaranteed that $T \leqslant 5$.

• For all data in all test points, it is guaranteed that $m \leqslant n \leqslant 200, b_i \leqslant n$.

见题面 Input 部分

见题面 Output 部分