D. Board
time limit per test
2.5 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

You are given a matrix A of size M * N, where 0 ≤ Aij < K. The rows are numbered from 1 to M, the columns are numbered from 1 to N.

You are allowed to apply 2 types of operations:

  • Choose a value R (1 ≤ R ≤ M). For each j where 1 ≤ j ≤ N, apply A(R, j) = (A(R, j) + 1) % K. (In other words, for each cell in the R-th row, add 1 modulo K).
  • Choose a value C (1 ≤ C ≤ N). For each i where 1 ≤ i ≤ M, apply A(i, C) = (A(i, C) + 1) % K. (In other words, for each cell in the C-th column, add 1 modulo K). Find the minimum number of operations, to transform the given matrix into all 0.
Input

The first line contains three integers, M, N and K, (1 ≤ M, N ≤ 1000, 1 ≤ K ≤ 109).

The following M lines describe the matrix. Each line consists of N numbers Aij (0 ≤ Aij < K).

Output

The minimal number of operations is displayed in the first line.

In the following line you should output M numbers describing how many operations were applied for each row (starting from the first row).

In the following line you should output N numbers describing how many operations were applied for each column (starting from the first column).

Examples
Input
3 3 2
0 0 0
1 1 1
1 1 1
Output
2
0 1 1 
0 0 0