W nadchodzącym roku 20XX w Japonii odbędzie się Międzynarodowy Festiwal Informatyczny (International Omatsuri in Informatics). W ramach przygotowań do tego wydarzenia powierzono Ci zadanie zaprojektowania logo tego festiwalu.

Logo Międzynarodowego Festiwalu Informatycznego za każdym razem powstaje na bazie pewnego ustalonego rysunku. Rysunek ten składa się z pewnych pól wybranych z prostokątnej siatki kwadratowych pól o szerokości $W$ pól w poziomie i wysokości $H$ pól w pionie. Tym razem postanowiłeś pokolorować ten rysunek barwami flagi narodowej Japonii — na czerwono i biało — aby stworzyć z niego logo. Aby nie komplikować pracy związanej z kolorowaniem, na $1$ polu można użyć tylko $1$ koloru.

Aby zdecydować, jak najlepiej rozmieścić kolory, poprosiłeś o radę znajomego projektanta. Według jego wspaniałego zmysłu estetycznego pożądany jest projekt, w którym zarówno obszar pomalowany na czerwono, jak i obszar pomalowany na biało tworzą figury osiowosymetryczne. Ponadto, biorąc pod uwagę równowagę kolorów, powiedział Ci również, że liczba pól pomalowanych na czerwono powinna wynosić $K$. Ponieważ nie zdradził Ci sposobu pokolorowania spełniającego te warunki, musisz znaleźć go samodzielnie. Mając dany rysunek oraz wartość $K$, napisz program, który znajdzie $1$ pokolorowanie spełniające warunki.

Wejście

W wierszu $1$ zapisane są $3$ liczby całkowite $W, H, K$ ($1 \le W \le 40$, $1 \le H \le 40$, $1 \le K \le WH - 1$) oddzielone spacjami. Oznaczają one odpowiednio szerokość i wysokość danego rysunku oraz liczbę pól, które należy pomalować na czerwono.

Kolejne $H$ wierszy przedstawia dane rysunku. W wierszu $i + 1$ ($1 \le i \le H$) zapisanych jest $W$ liczb równych $0$ lub $1$, oddzielonych spacjami. Gdy $j$-ta liczba całkowita ($1 \le j \le W$) w wierszu $i + 1$ wynosi $1$, oznacza to, że pole znajdujące się w $i$-tym wierszu od góry i $j$-tej kolumnie od lewej jest używane na rysunku; gdy wynosi $0$, oznacza to, że pole to nie jest używane na rysunku. Na rysunku zawsze używane są co najmniej $2$ pola. Gwarantuje się, że wartość $K$ jest ostro mniejsza od liczby pól używanych na rysunku.

Dla każdego zestawu danych wejściowych używanego podczas oceniania istnieje co najmniej $1$ pokolorowanie spełniające warunki.

Wyjście

Wyjście należy wypisać na standardowe wyjście. Wypisz liczby całkowite opisujące pokolorowanie — po $W$ liczb oddzielonych spacjami w każdym z $H$ wierszy. Gdy $j$-ta liczba całkowita w $i$-tym wierszu wynosi $1$, oznacza to pomalowanie pola w $i$-tym wierszu od góry i $j$-tej kolumnie od lewej na czerwono; gdy wynosi $2$, oznacza to pomalowanie tego pola na biało. Dla pól nieużywanych na rysunku wypisz $0$.

Jeśli istnieje wiele możliwych pokolorowań, możesz wypisać dowolne z nich.

Kryteria oceniania

Wśród danych używanych do oceniania, dla $20\%$ punktów zachodzi $W, H \le 5$.

Przykładowe wejście 1

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

Przykładowe wyjście 1

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

To wyjście odpowiada następującemu pokolorowaniu. Szare pola oznaczają pola pomalowane na czerwono, a białe pola oznaczają pola pomalowane na biało. Linia kreskowana i linia kropkowana są odpowiednio osiami symetrii obszaru czerwonego i obszaru białego.

Następujące pokolorowania nie spełniają warunków: