No.65 Small Grid and Score

時間制限:$1.0sec$ / メモリ制限:$1024MB$ / tester:square1001 kotamanegi

問題文

E869120 君は、以下のようなグリッドを作りました。

  • グリッドのサイズは、H * W である。左上が (1, 1)、右下が (H, W)、上から i 番目左から j 番目のマスをマス (i, j) とします。
  • グリッドのマスの状態は 「何も書かれていない」「壁のマス」「+1 のマス」「x2 のマス」の 4 種類あります。

さて、E869120 君はグリッドを作っただけではつまらないので、グリッドに「得点」という概念を付けることにしました。
「得点」は、以下のように計算されます。

  • マス (1, 1) から (H, W) まで、右か下にしか進まずに、壁のマスを通らずに移動できる方法における「ポイント」の合計(ただし、マス(1,1)も通ったものとして扱う)
  • 「ポイント」は、最初 1 であり 「+1」のマスを通ると 1 加算され「x2」のマスを通ると 2 が掛けられます。

例えば、以下のグリッドにおける「得点」は以下のようになります。


==================
 |    | +1 | x2 |
==================
 | x2 | 壁 | x2 |
==================
 |    |    | +1 |
==================

####13:29修正　黒いマス -> 壁のマス

マス (1, 1) から (3, 3) に進む方法は 2 通りあり、それぞれの「ポイント」の値は？
(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3) : ポイントの値は (1, 1) の時点で 1, (1, 2) の時点で +1 されるので 2, (1, 3) の時点で x2 されるので 4, (2, 3) の時点で x2 されるので 8, (3, 3) の時点で +1 されるので 9 となります。
(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) : ポイントの値は (1, 1) の時点で 1, (2, 1) の時点で x2 されるので 2, (3, 1) の時点では変わらず 2, (3, 2) の時点では変わらず 2, (3, 3) の時点で +1 されるので 3 となります。 2 つのルートのポイントは 9, 3 なので、「得点」の値は 9 + 3 = 12 となります。

課題

「得点」の値がちょうど N となるようなグリッドを 1 つ構成してください。 ただし、構成するグリッドの H, W の値によって、得点が変わります。

制約

  • $0$ ≦ $N$ ≦ $10^{18}$

部分点

小課題 1 [80 点]

  • $N ≦ 10000$ を満たす。
  • $H,W ≦ 1000$でなければならない。

小課題 2 [920 点]

  • $N ≦ 10^{18}$ を満たす。
  • そこで、全てのケースにおける max(H, W) の値の最大値を L とする。L の値によって得点が変わる。
    • $1001 ≦ L $ -> 0 点
    • $101 ≦ L ≦ 1000$ -> 100 点
    • $66 ≦ L ≦ 100$ -> 140 点
    • $37 ≦ L ≦ 65$ -> 220 点
    • $28 ≦ L ≦ 36$ -> 300 点
    • $21 ≦ L ≦ 27$ -> 2060 - 60L 点
    • $1 ≦ L ≦ 20$ -> 920 点

入力形式

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


N

出力



H W
c[1][1] c[1][2] c[1][3] ... c[1][W]
c[2][1] c[2][2] c[2][3] ... c[2][W]
c[3][1] c[3][2] c[3][3] ... c[3][W]
...
c[H][1] c[H][2] c[H][3] ... c[H][W]

それぞれのマスについて、

  • 壁の場合： '#'
  • +1 の場合：'1'
  • x2 の場合：'2'
  • 何もない場合：'.'

ただし、空白区切りではない。

入出力例

入力1 

12
出力1 

3 3
.12
2#2
..1
入力2 

192
出力2 

3 3
222
222
222