横一列に並んだ 個のマスがあり、左から順にマス と呼びます。SF くんはこのマスの上に住んでいて、よくゴミを散らかします。
そこで、お掃除ロボットを用意することにしました。
マスの初期状態が として与えられます。ここで、マスのそれぞれはゴミの落ちていない状態( .
)と、
ゴミの落ちている状態( #
)のどちらか一方を取り、 がマス の状態を表します。
SF くんは、この状態から 日間過ごすことにしました。 日目 には、以下のような出来事が起こります。
#
であるなら、掃除ロボットが起動し、マス に置かれる。#
ならば、マス へ移動する。そうでないならマス で停止する。.
になる。#
にする。日経過したあとの最終的なマスの状態を求めてください。
#
と .
からなる長さ の文字列最終的なマスの状態を、 と同じ形式で出力せよ。 即ち、長さ の文字列 であって、 の全てについて が最終的な 番目のマスの状態に一致するようなものを出力せよ。
3 3 #.#
...
以下のように状態が変化します。
..#
となる。.##
となる。###
となる。...
となる。28 980563679 #####.#.##...#....#.####.###
.#####...#.##.#..##..##.#..#
日数が非常に大きいことがありますが、ロボットが壊れたりゴミが尽きたりすることはありません。