Karakuri Doll

からくり人形師の JAG 氏は，長年の研究の果てに，伝統技術と最新技術を融合させたすばらしいお茶汲み人形の開発に成功した．このお茶汲み人形は，下の図のように格子に区切られた家の中で，台所（K）でお茶の入った湯飲みを乗せるとそれを主人（M）の居場所まで持っていき，主人が飲み終わった湯飲みを乗せると台所まで戻っていくという仕事をする．ただし，この人形は台所と主人の間の往復経路を自分で見つけられるほど賢くはない．使用者はこの人形にプログラムをあらかじめ入力して，人形がきちんと往復できるようにする必要がある．

図 F-1: 家の構造の例

人形が受理する命令は「左に曲がる」と「右に曲がる」の 2 つであり，人形に入力可能なプログラムは命令の有限な列である．人形は台所を出発した後，壁（図中「#」で表されたマス）にぶつかるまで前進し，壁にぶつかると最初の命令に従って左または右に方向転換する．以降，再び壁にぶつかるまで前進し，ぶつかったら次の命令を実行し，以下同様に物事が進む．方向転換してもなお壁にぶつかって前進できないときは，その場所から移動しないまま次の命令を実行する．壁にぶつかったとき，実行する命令が残っていなければ人形は停止する．これをプログラムの順実行と呼ぶ．

主人の居場所から台所に戻るときは，プログラムの命令列を逆順に実行し，さらに左右反対に方向転換する．これをプログラムの逆実行と呼ぶ．命令の実行順序および方向転換以外の挙動は順実行と同じである．

たとえば，上の図の家で，この人形に「右，右，左」というプログラムを与えると，往路では地点 a で右，地点 b で右，地点 c で左にそれぞれ方向転換して主人の居場所に到着する．また，復路では地点 c で右，地点 b で左，地点 a で左にそれぞれ方向転換して台所に帰還する．一方，「左，左」というプログラムを与えると，人形はまず地点 a で左に方向転換する．直進しようとするが，そのまま左側の壁にぶつかるため，地点 a にとどまったまま 2 番目の命令にしたがって左に方向転換する．そして直進して台所まで戻ってきたところで壁にぶつかり，命令が残っていないので停止する．

ところで，JAG 氏は大きな過ちを犯していた．実は，どのようなプログラムを与えても主人の居場所までたどり着けない場合が存在するのである．また，主人の居場所に着いたとしても，湯飲みを台所まで持って帰れない場合もある．

あなたの仕事は，ある家の中でこの人形を使ったときに，この人形が主人の居場所に到着できるか，そして台所に帰還できるかを判断するプログラムを書くことである．

入力は複数のデータセットからなり，最後に 0 0 と書かれた行が入力の終わりを示す．データセットの数は 128 個以下である．

各データセットの最初の行には，家の大きさを表す 2 つの整数 W, H がスペース区切りで書かれる．これらの整数は 3 ≦ W ≦ 64, 3 ≦ H ≦ 16 を満たす．続く H 行は部屋の構造を意味する．各行は W 文字から構成され，「#」は壁を，「.」（ピリオド）は床を，「K」は台所を，「M」は主人の居場所をそれぞれ示す．これら以外の文字は含まれない．

この家の最外部は，常に壁（「#」）であることが保証されている．また「K」と「M」は，各データセットについて常に 1 つずつ存在して，3 方向が壁（「#」），残りの 1 方向が床（「.」）であると仮定してよい．

各データセットに対して，以下の記述のとおりにメッセージを 1 行に出力しなさい．

• どのようなプログラムを与えても主人の居場所に到着しない場合は「He cannot bring tea to his master.」
• 主人の居場所には到着するが，その後に台所に帰還するようにプログラムできない場合は「He cannot return to the kitchen.」
• 主人の居場所に到着して，台所に帰還するようにプログラムできる場合は「He can accomplish his mission.」

ここで，主人の居場所に到着するとは，人形を台所に置いて壁のない方向に向けた状態から，プログラムを順実行したときに，停止時点において主人の居場所に人形が存在することを指す．台所に帰還するとは，人形を主人の居場所に置いて壁のない方向に向けた状態から，プログラムを逆実行したときに，停止時点において台所に人形が存在することを指す．停止時点における人形の向きは問わない．また，往路，復路ともに，経路の途中で台所または主人を通過しても構わない．ただし，経路の途中で台所または主人を通過したとしても，停止時点において人形がそれ以外の場所にいるときは，主人の居場所に到着した，あるいは台所に帰還したとはみなされない．