Description

Given $n \times m$ points arranged into $n$ rows and $m$ columns, there are weighted bidirectional edges between adjacent points. That is, let $(i, j)$ be the point on the $i$-th row and the $j$-th column, for all $1 \le i, i' \le n$ and $1 \le j, j' \le m$, there is an edge between $(i, j)$ and $(i', j')$ if and only if $|i - i'| + |j - j'| = 1$.

BaoBao will begin his journey at any point $(p, 1)$ on the first column and finish the journey at any point $(q, m)$ on the last column. He can travel along the edges in both directions. The distance of a path is defined as the sum of the weight of the edges in the path. Among all the paths from the first column to the last column, BaoBao will choose the shortest path.

Little Cyan Fish hopes BaoBao to better enjoy the journey, so he tries to increase the weight of some edges before BaoBao begins traveling. Specifically, Little Cyan Fish can increase the weight of any edge by $1$ in one operation. He hopes the distance of BaoBao's path can increase by $k$ after all operations. Please help him calculate the minimum number of operations needed and output the corresponding solution.

Input Format

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$ ($1\leq n\times m\leq 500$, $2\leq n,m\leq 500$, $1\leq k\leq 100$) indicating the number of rows and columns, and the increment on the length of the shortest path.

For the following $n$ lines, the $i$-th line contains $(m - 1)$ integers $r_{i,1}, r_{i,2}, \cdots, r_{i,m-1}$ ($1\leq r_{i,j}\leq 10^9$) where $r_{i,j}$ indicates the weight of the edge between $(i,j)$ and $(i,j+1)$.

For the following $(n - 1)$ lines, the $i$-th line contains $m$ integers $c_{i,1}, c_{i, 2}, \cdots, c_{i,m}$ ($1\leq c_{i,j}\leq 10^9$) where $c_{i,j}$ indicates the weight of the edge between $(i,j)$ and $(i+1,j)$.

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

Output Format

For each test case:

First output one line containing one integer indicating the minimum number of operations needed.

Then output $n$ lines. The $i$-th line contains $(m - 1)$ integers $r'_{i,1}, r'_{i,2}, \cdots, r'_{i,m-1}$ ($1\leq r'_{i,j}\leq 2\times 10^9$) separated by a space, where $r'_{i,j}$ indicates the weight of the edge between $(i,j)$ and $(i,j+1)$ after all operations.

Then output $(n - 1)$ lines. The $i$-th line contains $m$ integers $c'_{i,1}, c'_{i,2}, \cdots, c'_{i,m}$ ($1\leq c'_{i,j}\leq 2\times 10^9$) separated by a space, where $c'_{i,j}$ indicates the weight of the edge between $(i,j)$ and $(i+1,j)$ after all operations.

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

Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!

2
3 4 6
2 1 15
7 1 9
13 3 2
3 6 1 2
5 2 15 3
3 3 3
1 1
2 2
3 3
1 1 1
2 2 2

9
2 3 15
7 1 10
13 3 4
3 6 3 2
5 4 15 3
4
4 1
3 2
3 3
1 1 1
2 2 2

Hint

The first sample test case is illustrated below. The graph on the left is the original graph and the graph on the right is the graph after increasing the weight of some edges. Shortest paths of each graph are marked by red lines.

:::align{center} :::