Im kommenden Jahr 20XX wird das Internationale Informatik-Fest (International Omatsuri in Informatics) in Japan stattfinden. Zur Vorbereitung auf diese Veranstaltung wurdest du damit beauftragt, das Logo für dieses Fest zu entwerfen.

Das Logo des Internationalen Informatik-Fests wird jedes Mal auf der Grundlage eines bestimmten festen Bildes erstellt. Dieses Bild besteht aus einigen Feldern eines rechteckig angeordneten Gitters aus quadratischen Feldern mit $W$ Feldern in der Breite und $H$ Feldern in der Höhe. Diesmal hast du beschlossen, dieses Bild in den Farben der japanischen Nationalflagge – Rot und Weiß – einzufärben, um daraus das Logo zu gestalten. Um die Färbearbeit nicht unnötig kompliziert zu machen, darf für $1$ Feld nur genau $1$ Farbe verwendet werden.

Um zu entscheiden, wie die Färbung am besten erfolgen soll, hast du einen befreundeten Designer um Rat gefragt. Nach seinem wunderbaren ästhetischen Empfinden ist ein Design wünschenswert, bei dem sowohl der rot gefärbte Bereich als auch der weiß gefärbte Bereich jeweils eine achsensymmetrische Figur bilden. Zudem sagte er dir mit Blick auf die Farbbalance, dass die Anzahl der rot zu färbenden Felder $K$ betragen sollte. Da er dir keine Färbung verraten hat, die diese Bedingungen erfüllt, musst du selbst eine solche Färbung finden. Schreibe ein Programm, das bei gegebenem Bild und gegebenem Wert von $K$ genau $1$ Färbung bestimmt, die alle Bedingungen erfüllt.

Eingabe

In Zeile $1$ stehen $3$ durch Leerzeichen getrennte ganze Zahlen $W, H, K$ ($1 \le W \le 40$, $1 \le H \le 40$, $1 \le K \le WH - 1$). Diese geben die Breite und die Höhe des gegebenen Bildes sowie die Anzahl der rot zu färbenden Felder an.

Die folgenden $H$ Zeilen stellen die Daten des Bildes dar. In Zeile $i + 1$ ($1 \le i \le H$) stehen $W$ durch Leerzeichen getrennte Zahlen, jeweils $0$ oder $1$. Wenn die $j$-te ganze Zahl ($1 \le j \le W$) in Zeile $i + 1$ gleich $1$ ist, bedeutet dies, dass das Feld in der $i$-ten Zeile von oben und der $j$-ten Spalte von links im Bild verwendet wird; ist sie $0$, wird dieses Feld nicht im Bild verwendet. Im Bild werden stets mindestens $2$ Felder verwendet. Es wird garantiert, dass der Wert von $K$ echt kleiner als die Anzahl der im Bild verwendeten Felder ist.

Für jede zur Bewertung verwendete Eingabe existiert mindestens $1$ Färbung, die die Bedingungen erfüllt.

Ausgabe

Die Ausgabe muss auf die Standardausgabe erfolgen. Gib die ganzen Zahlen, die die Färbung darstellen, über $H$ Zeilen hinweg mit jeweils $W$ durch Leerzeichen getrennten Zahlen pro Zeile aus. Wenn die $j$-te ganze Zahl in Zeile $i$ gleich $1$ ist, bedeutet dies, dass das Feld in der $i$-ten Zeile von oben und der $j$-ten Spalte von links rot gefärbt wird; ist sie $2$, wird dieses Feld weiß gefärbt. Für Felder, die nicht im Bild verwendet werden, gib $0$ aus.

Falls mehrere Färbungen möglich sind, darfst du eine beliebige davon ausgeben.

Bewertungskriterien

Unter den zur Bewertung verwendeten Testdaten gilt für $20\%$ der Punkte $W, H \le 5$.

Beispieleingabe 1

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

Beispielausgabe 1

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

Diese Ausgabe entspricht der folgenden Färbung. Graue Felder stehen für rot gefärbte Felder und weiße Felder stehen für weiß gefärbte Felder. Die gestrichelte Linie und die gepunktete Linie sind die Symmetrieachsen des roten Bereichs bzw. des weißen Bereichs.

Die folgenden Färbungen erfüllen die Bedingungen nicht: