画像を圧縮する
あなたが現在勤務している企業では、白黒画像を大量に扱う巨大なデータセットを保持しています。しかし、その画像データは大きな容量を必要とするため、ストレージ節約の目的で圧縮アルゴリズムを実装してほしいと依頼されました。
この問題では、黒い画素を0、白い画素を1で表した の白黒画像に対して、
K% の階層的圧縮 (hierarchical compression) を実行する必要があります。階層的圧縮を適用すると、アルゴリズムはまず画像全体から始めて、画像を左上・右上・左下・右下の4つに等分割します。次に、それぞれの部分を再び4つに分割していき、同じ手順を繰り返します。ただし、現在の部分領域が単一の色に支配されている場合、その部分全体をその色で塗りつぶして分割を終了します。ここで「単一の色に支配されている」とは、その部分のうち
K% 以上を1つの色が占めることを意味します。最初に与えられた画像をこの手法で圧縮した後、その結果の画像を出力することが求められます。
入力
最初の行には、2つの整数
N (1 ≤ N ≤ 64) と K (51 ≤ K ≤ 100) が与えられます。なお、N は 2 のべき乗であることが保証されています。続く
N 行にわたって、各行に N 個の 0 または 1 が与えられます。出力
プログラムは、圧縮後の画像を出力してください。
例
Input
8 75
11111000
11110000
11000011
11000011
11000100
00000100
00010011
00010011Output
11110000
11110000
11110011
11110011
00000100
00000100
00000011
00000011説明
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB