問題文

全てのマスが白く塗られた $N \times N$ グリッドがあり、その上に Alice がいます。上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と表すとき、Alice の現在地は $(s_r, s_c)$ です。

Alice は上下左右に隣接したマスへの移動を繰り返し、目的地 $(t_r, t_c)$ まで移動しようとしています。しかし、それを見ていた Bob は、いくつかのマスを黒く塗り、Alice を遠回りさせるいたずらを実行することにしました。

白から白、黒から黒のように、直前と同じ色のマスに移動する際にかかる移動時間は $1$ ですが、白から黒、黒から白のように、直前と異なる色のマスに移動する際にかかる移動時間は $2$ です。

さて、Bob は Alice の現在地と目的地を除いて、好きなマスを好きな数だけ黒く塗ることができます。このとき、どこを塗れば Alice が現在地から目的地まで移動するのにかかる時間の最小値をちょうど $K$ にすることができるでしょうか？

Bob の代わりに考えてあげましょう。条件を満たす塗り方が存在しない場合は -1 を出力してください。

制約

• 入力は全て整数
• $2 \leq N \leq 1000$
• $1 \leq K \leq 10^9$
• $1 \leq s_r, s_c, t_r, t_c \leq N$
• $(s_r, s_c) \neq (t_r, t_c)$

入力

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

$N\ K$
$s_r\ s_c$
$t_r\ t_c$

出力

条件を満たす塗り方が存在する場合は、以下の形式でその一例を出力してください。ただし、$S_i$ は長さ $N$ の文字列であり、$S_i$ の $j$ 文字目はグリッドの上から $i$ 行目、左から $j$ 列目のマスを黒く塗る場合 #、白く塗る場合 . となります。

条件を満たす塗り方が存在しない場合は -1 を出力してください。

$S_1$
$S_2$
$\vdots$
$S_N$

最後に改行してください。

ビジュアライザ

出力結果のWeb版ビジュアライザがこちらで提供されています。

コンテスト中における、ビジュアライズ結果の共有や解法・考察に関する言及は禁止されています。ご注意下さい。

また、ビジュアライザの仕様に関する質問は原則受け付けません。あくまで補助ツールとしてご利用ください。

サンプル

サンプル1

入力

5 10
2 1
4 5

出力

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

出力例において、かかる時間が最小となる経路の一例は下図のようになり、$(2, 1) \rightarrow (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4) \rightarrow (3, 5) \rightarrow (4, 5)$ です。

2 3
1 1
2 2

-1