/ 
Time Limit: 3 sec / Memory Limit: 128 MB
問題文
とある大学の魔法学部の生徒であるK君は広大な屋敷に住んでいる． 屋敷の裏には林が広がっていたが，所々木が生えていない箇所があった． このままでは屋敷からの見た目が悪いと感じたので，K君は木が生えていない箇所に木を植えることに決めた． 魔法使いの卵であるK君は使い魔を召喚することが出来るので，植林の作業を使い魔にやらせようと考えた．
林は H \times W 個のセルを持つ長方形領域とみなすことが出来る． 各セルは木が1本生えているか1本も生えていないかのどちらかである． K君はこの H \times W 個のセルのどれか 1 つを指定し，そこに使い魔を召喚する． しかしK君はまだ未熟者なので，魔力を調節することが出来ず，使い魔を召喚するときは必ず 5 匹召喚してしまう． さらに悪いことに，K君が召喚する使い魔はひねくれもので，訪れたセルに木が生えていない場合はそこに木を植えるが，訪れたセルに既に木が生えている場合はそのセルの木を消してしまう． 召喚された使い魔のうちの 4 匹は，指定されたセルを始点として東西南北に散らばり1直線上を進み，1つ1つセルを訪れていく．これらの使い魔は林の外に出ると消える． 残りの使い魔は指定されたセルのみを訪問し，その後直ちに消える．
より正確に言えば，K君がセル (i, j) に使い魔を召喚すると，i 行目か或いは j 列目にある H+W-1 個のセルに対し， 木が生えていなければ木が植えられ，木が生えていれば木が消されるという操作が行われる．
召喚には多くの魔力を必要とするので，出来るだけ少ない召喚回数で林を木で覆いつくしたい． K君はどのセルに使い魔を召喚すれば最小の召喚回数で林を木で覆いつくすことが出来るだろうか．
入力形式
入力は以下の形式で与えられる．
H\ W\ a1,1\ ...\ a1,W\ ...\ aH,1\ ...\ aH,W
ai,j が 1 ならセル (i,j) に木が生えていることを意味し, 0なら生えていないことを意味する．
出力形式
もし林を木で覆いつくすことが不可能なら，1行に Impossible を出力せよ．
そうでなければ，召喚回数を最小にするような召喚手順を以下の形式で H 行に出力せよ．
b1,1\ ...\ b1,W\ ...\ bH,1\ ...\ bH,W
bi,j は 0 もしくは 1 でなければならず, 1 ならセル (i,j) に使い魔を召喚する事を意味し，0 なら召喚しない事を意味する．
2回同じ場所に使い魔を召喚しても意味が無いことに注意せよ．召喚回数を最小にするような召喚手順が複数ある場合はどれを出力しても良い．
制約
- 2 ≤ H，W ≤ 1000
- H，W は偶数
- ai,j \in \{0, 1\}
この問題の判定には，3 点分のテストケースのグループが設定されている． このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす．
- H \times W ≤ 20
入出力例
入力例 1
4 4 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0
出力例 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
セル (1,1) とセル (4,4) に使い魔を召喚することで林を木で覆いつくすことが出来る．
Writer: 田村和範 Tester: 花田裕一朗