402370: GYM100739 D Board

You are given a matrix A of size M * N, where 0 ≤ A_ij < 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.

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

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

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).

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

2
0 1 1 
0 0 0