ロゴマーク (Logo)

来る 20XX 年, 国際情報学祭り (International Omatsuri in Informatics) が日本で開かれること になった．そこでその開催に向けて，あなたはこの祭りのロゴマークを作成することになった．

国際情報学祭りのロゴマークは，毎回，ある一定の絵が下地となって作られている．この絵 は，横 W 個，縦 H 個の長方形状に並んだ正方形のマス目のうちのいくつかのマス目から構成 されている．今回あなたは，この絵を日本の国旗の色である赤と白で塗り分けてロゴマークと することにした．色塗りの作業を煩雑にしないため，1 つのマス目には 1 つの色しか使うことは できない．

どのように塗り分けるのがよいかを決めるため，あなたは知り合いのデザイナーに助言を求 めた．彼のすばらしい美的感覚によれば，赤く塗られた領域，白く塗られた領域がどちらも線 対称な図形になっているデザインが望ましいという．また，色のバランスを考えると，赤く塗 るマス目の個数は K 個にするのが良いとも言われた．これらの条件にしたがった塗り方を彼は 教えてくれなかったので，あなたは自分で塗り方を求める必要がある．絵および K の値が与え られたとき，条件をみたす塗り方を 1 つ求めるプログラムを作成せよ．

入力の 1 行目には，3 つの整数 W, H, K(1 ≤ W ≤ 40, 1 ≤ H ≤ 40, 1 ≤ K ≤ WH − 1) が空白を区切りとして書かれている．これは，与えられた絵の横幅，縦 幅と，赤く塗るマス目の個数を表す．

続く H 行は絵のデータを表す．i + 1 行目 (1 ≤ i ≤ H) には W 個の 0 または 1 が空白を区切 りとして書かれている．i + 1 行目の j 個目 (1 ≤ j ≤ W) の整数が 1 のときは，上から i 番目， 左から j 番目のマス目が絵に使われていることを，0 のときはそのマス目が絵に使われていない ことを表す．絵には必ず 2 つ以上のマス目が使われている．K の値は，絵に使われているマス 目の個数より小さいことが保証される．

採点に使われるどの入力においても，条件をみたす塗り方は少なくとも 1 つ存在する．

出力は，標準出力に行うこと．塗り方を表す整数を，1 行に空白区切りで W 個，H 行にわたって出力せよ．i 行目の j 個目の整数が 1 の場合，上から i 番目，左から j 番目のマス 目を赤く塗ることを，2 の場合，そのマス目を白く塗ることを表す．絵に使われていないマス目 については 0 を出力せよ．

この出力は次のような塗り方に対応している. 灰色のマスは赤く塗ることを, 白のマスは白く 塗ることを表す. 破線と点線がそれぞれ赤い領域, 白い領域の対称軸である.

次のような塗り方は条件をみたさない：

赤い領域が線対称でない	赤く塗られたマスの個数が 2 でない