A. Two-star Contest
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Education experts are going to rate $$$n$$$ contests due to whatever reasons. The experts have already decided on the rating of each contest, where the $$$i$$$-th contest is rated as a $$$s_i$$$-star contest.

It is said that each contest is rated according to $$$m$$$ properties, where the $$$j$$$-th property of the $$$i$$$-th contest is indicated as $$$p_{i, j}$$$, whose value ranges from $$$0$$$ to $$$k$$$ (both inclusive). The score of a contest is calculated as the sum of all its $$$m$$$ properties. That is, let $$$v_i$$$ be the score of the $$$i$$$-th contest, we have $$$v_i = \sum\limits_{j=1}^m p_{i, j}$$$.

It would be natural for a contest with more stars to have a higher score. The experts require that, for any two contests $$$1 \le i, j \le n$$$, if $$$s_i \gt s_j$$$, then there must be $$$v_i \gt v_j$$$. Unfortunately, the experts forgot to collect values for some (or even all) properties of some contests. As the assistant of the experts, you're required to fill in the missing values so that the constraint stated above holds for any two contests.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n \le 4 \times 10^5$$$, $$$1 \le m \le 4 \times 10^5$$$, $$$n \times m \le 4 \times 10^5$$$, $$$1 \le k \le 10^9$$$) indicating the number of contests, the number of properties of each contest, and the upper bound of the value of each property.

For the following $$$n$$$ lines, the $$$i$$$-th line first contains an integer $$$s_i$$$ ($$$1 \le s_i \le 10^9$$$) indicating the number of stars the $$$i$$$-th contest is rated. Then $$$m$$$ integers $$$p_{i, 1}, p_{i, 2}, \cdots, p_{i, m}$$$ follow ($$$-1 \le p_{i, j} \le k$$$). If $$$p_{i, j} = -1$$$ then the value of the $$$j$$$-th property of the $$$i$$$-th contest is missing and it is your quest to fill it in; Otherwise if $$$p_{i, j} \ge 0$$$ then the value of the $$$j$$$-th property of the $$$i$$$-th contest is given and you should not change it.

It's guaranteed that the sum of $$$n \times m$$$ of all test cases will not exceed $$$4 \times 10^5$$$.

Output

For each test case:

If it is possible to fill in all the missing properties while satisfying the constraint, first output Yes in one line. Then output $$$n$$$ lines where the $$$i$$$-th line contains $$$m$$$ integers $$$q_{i, 1}, q_{i, 2}, \cdots, q_{i, m}$$$ ($$$0 \le q_{i, j} \le k$$$) separated by a space, indicating the $$$m$$$ properties of the $$$i$$$-th contest after you fill in the missing values. If $$$p_{i, j} = -1$$$ then $$$q_{i, j}$$$ should be the value you fill in; Otherwise if $$$p_{i, j} \ge 0$$$ then $$$q_{i, j} = p_{i, j}$$$. If there are multiple valid answers, you can output any of them.

If it is not possible to satisfy the constraint, just output No in one line.

Example
Input
5
3 4 5
5 1 3 -1 -1
2 -1 5 -1 5
3 3 -1 -1 4
2 3 10
10000 5 0 -1
1 10 10 10
2 3 10
10 1 2 3
100 4 5 6
2 3 10
100 1 2 3
10 4 5 6
2 3 10000
100 -1 -1 -1
1 -1 -1 -1
Output
Yes
1 3 5 4
0 5 0 5
3 3 2 4
No
Yes
1 2 3
4 5 6
No
Yes
2024 5 26
11 45 14
Note

For the second sample test case, even if we fill the only $$$-1$$$ with the maximum possible value $$$10$$$, the score of the first contest is still only $$$15$$$, which is not larger than the score $$$30$$$ of the second contest.