/ 
実行時間制限: 1 sec / メモリ制限: 256 MB
問題文
世界に誇る日本のおもちゃメーカーである Engrish 社は，業績不振から倒産の危機に追い込まれていました．一方今，世界ではお米を使った「ライスゲーム」が空前絶後の大ブームです！当然 Engrish 社はこのライスゲームブームを逃すまいと，日本での展開に力を入れることにしました．
このゲームを商品化し大量生産するには，とにかくお米がたくさん必要です！この案件の担当者は早速「モアモア・ライス・プリーズ！」と海外支社に連絡を入れたのですが……．
「なんてことだ…なんてことだ…．」
数日後，本社に大量に届いたのはおびただしい量のシラミでした．恐るべき数のシラミを前に絶望に打ちひしがれる社員たち，そして絶句する担当者．なぜこんなことが起きてしまったのでしょうか．
答えは明白です．担当者が "More! More! Lice please!" などという言語道断な要求を行い，海外支社の社員は何の疑問も持たずシラミを大量発注したためです．つまり，担当者の発音がすべての惨劇（カタストロフィー）を生んだのです．全ての罪は担当者にあります．会社は悪くありません．
大量の負債を抱えて手に入れた大量のシラミ，もはやどうしていいのか誰にも分かりません．倒産待ったなしというこの状況において，このシラミをどうにか利益に繋げなければ確実に会社は倒産します．
そんなわけで，Engrish 社は Lice Game というものを考えだすことにしました．Lice Game はシラミをふんだんに用いたゲームで，楽しく生き物の生態を学ぶための子供向けゲームです．
このゲームは，グリッドに区切られた培養ガラスの上で行われます．グリッドの各セルはシラミがいるかいないかの 2 パターンあり，一日目には好きなセルにシラミを配置できます．その後，決められたルールに従って一日ごとに世代交代していきます．あるセルに明日シラミがいるかどうかは，そのセルに今日シラミがいるかどうかと，そのセルの周辺にシラミがいるセルが何個あるかによって決まります．ただし，あるセルの周辺とは，そのセルと共有点をもつ 8 つのセルのことを言います．具体的なルールは以下のようになります．
- 今日シラミがいるセルで，周辺にシラミのいるセルが 2 個か 3 個の場合，明日もこのセルにはシラミがいる．（それ以外の個数の場合，明日このセルにはシラミはいなくなる）
- 今日シラミがいないセルで，周辺にシラミのいるセルが 3 個の場合，明日このセルにはシラミがいる．（それ以外の個数の場合，明日もこのセルにはシラミはいないままである）
このゲームは当然のことながら大ブレイクし，Engrish 社は息を吹き返すことができました．
ところで，JAPLJ さんは潔癖症なので「シラミは汚いのでNG」としきりに生物の尊厳を傷つけるような発言をしています．友人である kyuridenamida 君は，シラミのことをもっとよく正しく知ってもらうために，誕生日プレゼントとして JAPLJ に Lice Game を送りつけようとしています．
Lice Game のやっかいなところは，適当にシラミを配置すると大量にシラミが増殖してしまう可能性があることです．そうなってしまえば，JAPLJ さんにとって恐怖そのものです．また，このゲームは捨てるとすぐバレてしまうので，捨てることは決して許されません．
JAPLJ さんはこの非常事態をいち早く察知し，対策を練っています．JAPLJ さんは，このゲームを捨てずに済む方法として「どの日のゲームの状態を見ても，シラミの配置がまったく同じになるように，一日目にシラミを配置する」という方法を考えました．
Lice Game には決まった匹数のシラミが付属しており，一日目に付属のシラミをグリッド上に配置しなければなりません．何匹のシラミが付属しているかはゲームが届くまで分からないので，JAPLJ さんは付属のシラミが何匹いても大丈夫なようにプログラムを書くことにしました．
JAPLJ さんの友人であるあなたには，このプログラムを書くのを手伝ってもらいたいのです．
課題
問題文中のLice Gameは，言うまでもなくコンウェイのライフゲームと同じルールである．したがって，無限に広いグリッド上でライフゲームを行うことを考える．
ライフゲームでは，無限に広いグリッドの各セルに対し「生」または「死」の 2 通りの状態を考える．はじめ，グリッド上にいくつか「生」のセルを決め，他は「死」のセルとする．あるセルの次の世代の状態は，今のそのセルの状態およびそれに隣接するセルの状態によって決定される．あるセルに隣接するセルとは，そのセルと共有点を持つような 8 個のセルのことである．具体的なルールは以下のようになる．
- 「生」のセルであって，隣接するセルのうち「生」のセルが 2 個または 3 個であるようなものは，次の世代でも「生」のセルである．（そうでなければ次世代では「死」のセルとなる）
- 「死」のセルであって，隣接するセルのうち「生」のセルがちょうど 3 個であるようなものは，次の世代で「生」のセルとなる．（そうでなければ次世代でも「死」のセルのままである）
Wikipedia におけるライフゲームの記事にも同様のルールが記載されているので参考にするとよい．
いくつかの「生」のセルの配置が 8 方向に連結であるとは，どの「生」のセルから他のどの「生」のセルに対しても，隣接する「生」のセルのみを辿ることで到達できることをいう．N 個の「生」のセルからなる 8 方向に連結な配置で，何世代経っても配置が全く同じである（すなわちはじめ「生」であった N 個のセルはずっと「生」のままであり，他のセルはずっと「死」のままである）ようなものをひとつ求めるプログラムを書け．
入力
N
N は「生」のセルの個数を表す．
出力
S_1 S_2 … S_N
1 \leq i \leq N に対し S_i は N 文字の文字列であり，各文字がセルの状態を表す．この N 個の文字列は無限に広いグリッドのうち N \times N の部分を抜き出してきたものと考える．
各 S_i は . または # の 2 種類の文字のみからなり，. はそのセルが「死」の状態であること，# はそのセルが「生」の状態であることを表す．S_i 中に含まれる文字 # の総数は N でなければならない．また，文字 # は 8 方向に連結な配置でなければならない．
ただし，条件を満たすような「生」のセルの配置が存在しない場合には代わりに -1 とだけ出力せよ．
制限
すべての入力データは以下の制限を満たす．
- 1 \leq N \leq 1,000
採点基準
- N \leq 8 を満たす入力データすべてに対し正答した場合 1 点を与える．
- すべての入力データに対し正答した場合はさらに 99 点を与える．
入力例1
4
出力例1
.... .##. .##. ....
入力例2
1
出力例2
-1
statement: kyuridenamida