B - 経路が色々

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 800

問題文

次をすべて満たすようなマス目を構成してください。この問題の制約下で、このようなマス目が必ず存在することが保証されます。

  • マス目の各マスは白か黒で塗られている
  • マス目の縦横の長さをそれぞれ N,M としたとき、N,M1 以上 100 以下である
  • 一番左上のマスから一番右下のマスまで、白く塗られたマスだけを通って右または下に 1 マス進むことを繰り返して辿り着く方法はちょうど K 通りある

制約

  • 0 \leq K \leq 10^{18}
  • K は整数である

入力

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

K

出力

1 行目には、マス目の縦の長さ N と横の長さ M を空白区切りで出力せよ。

以後 N 行にわたって、NM 列にマス目の情報を出力せよ。ij 列の文字は #. のいずれかであり、 ij 列にあるマスが黒く塗られるなら # を、白く塗られるなら . を出力せよ。


入力例 1

4

出力例 1

3 4
...#
#...
.#..

一番左上のマスから一番右下のマスへ、右または下にのみ進むことを繰り返して辿り着く方法は、この例の場合 4 通りです。


入力例 2

18

出力例 2

4 4
...#
....
....
#...