問題文（一行）

S から G までの自己回避歩行 (self-avoiding walk) の数が N となるようなグリッドマップを作って出力して下さい。

問題文（詳細）

oneesan は以下の問題を高速に解くことが出来ます。

N,H,W と以下の条件を満たす高さ H、幅 W のグリッドマップが与えられます。

• 高さ H 幅 W のグリッドマップは、H 個の長さ W の文字列 S_1, S_2, \ldots, S_H で表される。
• 各マスはそれぞれ壁 # 、空き地 . 、始点 S 、終点 G の 4 文字のどれかで表される。
• 外周はすべて壁 # である。
• 始点 S と終点 G がそれぞれちょうど 1 マスずつ存在する。

グリッドマップ上で、S から G まで、上下左右に隣接した壁 # 以外のマスへの移動を繰り返して到達した時の、始点と終点を含めた通ったマスの列をパスとします。 パス P, Q が異なるとは、通ったマスの列の長さが違うか、P_i \ne Q_i となる i が存在することを言います。 パスの中でも、自己回避歩行 (self-avoiding walk) を、同じマスを 2 回通らないパスとします。 与えられたグリッドマップで、異なる自己回避歩行が何通りあるか調べ、それが N と等しいか答えて下さい。 等しい場合は Yes、そうでない場合は No と一行に出力して下さい。

oneesan は上述の能力を用いて自己回避歩行を数えるのが好きですが、自分でグリッドマップを生成して数えるのはつまらないと思いました。 そこで、oneesan はあなたにグリッドマップの生成をお願いすることにしました。

N が与えられるので、oneesan が Yes と出力するようなグリッドマップを出力して下さい。 ただし、グリッドマップには oneesan の仕様上の制限がいくつかあります。具体的には出力の項を読んで下さい。 この制約下で必ず解が存在することが言えます。また、制約さえ満たせばどのような解を出力しても構いません。

制約

• N は 0 \leq N \leq 2{,}019 を満たす整数

入力例 1

2

出力例 1

4 4
####
#S.#
#.G#
####

この出力以外にも正解となる出力が存在します。

入力例 2

8

出力例 2

5 9
#########
#S......#
#.#.#.#.#
#......G#
#########

入力例 3

184

出力例 3

6 6
######
#S...#
#....#
#....#
#...G#
######

入力例 4

1936

出力例 4

8 27
###########################
#.........................#
#.S####.#####.####...###..#
#...#.....#...#...#.#...#.#
#...#.....#...####..#.....#
#...#.....#...#.....#...G.#
#...#.....#...#......###..#
###########################