BINGO Card

問題文

$N$ 行 $N$ 列のマスからなるビンゴカードを、ビンゴせずにできるだけ多くの穴をあけてください。

厳密に述べます。

$N$ 行 $N$ 列のマスからなるビンゴカードについて、各マスは「穴があいている状態」もしくは「穴があいていない状態」のどちらかのみにすることができます。

ビンゴとは、次のいずれかの条件を満たす状態を指します。

1. ある行 $i$ ($1 \leq i \leq N$) において、すべての列 $j$ ($1 \leq j \leq N$) のマスに穴があいている状態

2. ある列 $j$ ($1 \leq j \leq N$) において、すべての行 $i$ ($1 \leq i \leq N$) のマスに穴があいている状態

3. 左上から右下に向かう対角線上のすべてのマスに穴があいている状態

4. 右上から左下に向かう対角線上のすべてのマスに穴があいている状態

あなたの目標は、ビンゴを成立させずに、穴があいたマスの個数を最大化することです。

制約

• $2 \leq N \leq 3000$
• 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

出力

題意を満たすビンゴカードを長さ $N$ の文字列 $N$ 個として出力せよ。 穴があいていないマスに対応する文字は . (ドット) とし、穴があいているマスに対応する文字は # とすること。

題意を満たすビンゴカードが複数存在する場合は、どれを出力しても正解となる。

サンプル

5

.####
####.
###.#
#.###
##.##

この出力例は $20$ 個のマスに穴があいているビンゴカードを表しています。

このビンゴカードでは、縦・横・ななめのすべての方向について、 $N$ 個連続して穴があいている箇所はありません。

また、穴をあけるマスの個数が $21$ 個以上のときは必ずビンゴしてしまうことが示せるため、これは問題文の条件を満たします。