Logo(ロゴマーク) - joi2009-day3

出典: 第8回日本情報オリンピック 春季トレーニング合宿

時間制限: 3秒

メモリ制限: 64MB

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

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

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

Input.

入力ファイルlogo.inの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 つ存在する.

Output.

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

複数の塗り方が可能な場合は, そのうちのどれを出力してもよい.

採点基準

採点に用いるデータのうち, 配点の20% 分についてはW,H ≤ 5である.

例

logo.in	標準出力
4 3 2 0 1 0 0 1 0 1 1 1 0 0 0	0 2 0 0 1 0 2 1 2 0 0 0

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

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