探検家の太郎君は迷宮の平面図を手に入れた.
この迷宮は二次元グリッド状で,平面図上の各マスは部屋に対応しており,各部屋に入れるかどうかは平面図に記されている.
北西の角,平面図上で左上の部屋にはこの迷宮の唯一の出入り口があり,残りの南西,南東,北東の 3 つの角の部屋にはそれぞれ宝箱が置かれている.
宝箱を手に入れるためには,宝箱の置かれている角の部屋まで移動しなければならない.
太郎君は出入り口のある部屋からスタートし,東西南北の四方向に隣接する入れる部屋への移動を繰り返し,最終的に 3 つの宝箱を全て回収して再び出入り口のある部屋に戻って来たい.
困ったことに,この迷宮は相当に荒れ果てていて,出入り口のある部屋以外は,たとえ入れる部屋でも床がとても壊れやすく,一度通ると崩れ落ちて,その部屋には二度と入れなくなってしまう.
全ての宝箱を回収して出入り口のある部屋に戻ることが可能か判定せよ.
入力は 100 個以下のデータセットからなる.
各データセットは次の形式で表される.
N M
c1,1...c1,M
...
cN,1...cN,M
1 行目には,南北方向の部屋の数 N と東西方向の部屋の数 M が与えられる.
N と M は整数であり, 2 ≤ N ≤ 50, 2 ≤ M ≤ 50 が成り立つ.
続く N 行には長さ M の文字列が与えられる.
i 行,j 列の文字 ci,j は,北端から i 番目,西端から j 番目の部屋 (i,j) の状態を表しており,入れる部屋であることを表すピリオド ('.') と入れない部屋であることを表すナンバーサイン ('#') のいずれかである.
迷宮の出入り口があるのは部屋 (1,1) であり,宝箱は (N,1),(N,M),(1,M) の 3 つの部屋に置かれている.これら 4 つの部屋は全て入ることができる.
与えられた N × M 室の部屋の外に出ることはできない.
入力の終わりは,2 つのゼロからなる行で表される.