Artifact Restoration

Time limit1sMemory limit512 MB

Summary

Given a grid with some unknown cells, fill unknowns with 0 or 1 so that the total number of people summed over all subrectangles is divisible by K.

Level: Hard8 of 10
Topics: Math, Number theory, Prefix sum, Implementation
Solved: No attempts yet

Problem

During construction work at a university in Seoul that produced constant noise and dust, a stone tablet presumed to be an ancient artifact was unearthed. The tablet is a grid with N rows and M columns, and each cell was either empty or held a drawing of one person. Unfortunately, the tablet was not unearthed intact, and some cells are broken so their contents cannot be identified.

Shortly afterward, related materials revealed the rule of this tablet. For every possible subrectangle, count the number of people inside it, and the sum of all those counts must be a multiple of K. The number 0 is a multiple of every number.

For example, consider the 2 × 2 tablet below.

The tablet above has the 9 subrectangles shown below.

The sum inside each subrectangle is 1, 0, 0, 1, 1, 1, 1, 1, 2, and their total is 8.

Based on the information obtained, the school asked the Department of Computer Science at Yonsei University to restore the tablet to one of its possible forms, and this task became a problem in the 2019 on-campus contest. Given the tablet and K, determine whether restoration is possible, and if it is, restore one tablet that satisfies the condition.

Input

The first line gives the number of rows N, the number of columns M of the tablet, and K as stated in the problem. (1 ≤ N, M ≤ 50, 2 ≤ K ≤ 2500)

From the second line to the N+1-th line, each line gives M integers ai,j separated by spaces. (ai,j ∈ { -1, 0, 1})

ai,j = -1 means the cell in row i and column j of the tablet is broken, ai,j = 0 means the cell is empty, and ai,j = 1 means the cell holds a drawing of one person.

Output

If restoration is possible, print 1 on the first line; if not, print -1.

If you printed 1 on the first line, then output one restored tablet over N lines of M integers, replacing every -1 in the matrix with 0 or 1 so that the condition of the problem holds. Every cell that was not -1 in the input must stay the same as the input, and every cell that was -1 must be restored to either 0 or 1.

If multiple tablets satisfy the condition, print any one of them.

Hint

A subrectangle is defined as follows. Number the rows from the top as 1, 2, …, N and the columns from the left as 1, 2, …, M. For some r1, r2, c1, c2 with 1 ≤ r1 ≤ r2 ≤ N and 1 ≤ c1 ≤ c2 ≤ M, it is the set of all cells whose row number is at least r1 and at most r2, and whose column number is at least c1 and at most c2. Every possible subrectangle means taking one rectangle for each distinct (r1, c1, r2, c2) satisfying the inequalities.

Examples3

Example 1
Input
```
2 2 8
1 0
0 -1
```
Expected output
```
1
1 0
0 1
```
Example 2
Input
```
2 2 7
1 0
0 -1
```
Expected output
```
-1
```

Example 3

Input

5 7 10
-1 -1 -1 -1 -1 -1 -1
-1 -1 0 0 0 -1 -1
-1 -1 0 1 0 -1 -1
-1 -1 0 0 0 -1 -1
-1 -1 -1 -1 -1 -1 -1

Expected output

1
1 1 1 1 1 1 1
1 1 0 0 0 1 1
1 1 0 1 0 1 1
0 0 0 0 0 0 0
1 1 1 1 1 1 1