Logo Mark

Time limit3sMemory limit1024 MB

Summary

Color the used cells of a W by H grid with exactly K red cells and the rest white, so that both the red and white regions are line-symmetric.

Level: Medium6 of 10
Topics: Implementation, Greedy, Geometry
Solved: No attempts yet

Problem

In the upcoming year 20XX, the International Omatsuri in Informatics will be held in Japan. You have been asked to create the logo mark for this festival.

The logo mark of this festival is always built on a fixed picture. The picture is made of some of the cells in a grid of W cells wide and H cells tall. This time, you will color the picture in red and white, the colors of the Japanese flag. To keep the coloring simple, each cell can have only one color.

To decide how to color it, you asked a designer you know for advice. He said that a design is best when both the red region and the white region are line-symmetric figures. Considering the color balance, he also said the number of red cells should be K. He did not tell you how to satisfy these conditions, so you need to find a coloring yourself. Given the picture and the value of K, write a program that finds one coloring that meets these conditions.

Input

The first line contains three integers W, H, and K separated by spaces, where $1 \le W \le 40$ , $1 \le H \le 40$ , and $1 \le K \le WH-1$ . They are the width of the picture, the height of the picture, and the number of cells to color red.

The next H lines describe the picture. Line i+1 (where $1 \le i \le H$ ) contains W integers separated by spaces, each either 0 or 1. The j-th integer on line i+1 (where $1 \le j \le W$ ) is 1 if the cell in row i from the top and column j from the left is used in the picture, and 0 if it is not.

The picture always uses at least 2 cells. K is guaranteed to be smaller than the number of cells used in the picture.

Output

Print the coloring as H lines with W integers each, separated by spaces. The j-th integer on the i-th line is 1 if the cell in row i from the top and column j from the left is colored red, and 2 if it is colored white. Print 0 for cells that are not used in the picture.

Hint

This output corresponds to the coloring below. Gray cells are colored red, and white cells are colored white. The dashed and dotted lines are the axes of symmetry of the red region and the white region, respectively.

The following colorings do not meet the conditions:



The red region is not line-symmetric	The number of red cells is not 2

Examples1

Example 1

Input

Expected output

0 2 0 0
1 0 2 1
2 0 0 0