一般人には知る由も無いことだが、この街は幽霊で溢れている。そのほとんどは無害なのだが、困ったことに、人を呪う悪霊も少なからずいるのだ。
あるところに、そんな悪霊と戦う少女がいた。彼女は昼間は何食わぬ顔で高校に通いながらも、夜になると街中を歩き回り、彷徨える魂を見付けては成仏させるのだ。
幽霊を成仏させるためにはまずその幽霊に接近する必要があるのだが、それは簡単なことではない。幽霊は物をすり抜けられるからだ。幽霊は民家に壁から侵入して勝手口から出て行ったり、信号の無い大通りを悠々と横断したりする。人間である彼女にはそんなことはできないので、幽霊を追跡するのはとても難しいのだ。
彼女は経験上、幽霊が規則的な動きをすることを知っていた。そこで彼女は、この情報を活用して幽霊を追跡することを考えた。
彼女のいる街は、(H × W)マスのグリッドとして表される。彼女も幽霊も、1分間に1回、次の5つの行動
のうちどれか1つを行うことができる。ただし、彼女は街の周囲に結界を張ったので、彼女も幽霊も街の外に出ることはできない。また、そのような行動をしようとした場合、代わりにその場に留まる。
それぞれのマスは '#' または '.' という文字によって表され、前者は幽霊だけが進入できるマスを、後者は両者が進入できるマスを表す。
幽霊の行動パターンは、L個の行動の列として与えられる。幽霊はこれらの行動を最初から順番に実行していき、全ての行動を実行し終わるとまた最初の行動に戻り、順に実行し続ける。
彼女と幽霊が N 分後に同じマスにいたならば、彼女と幽霊は時刻 N で遭遇したと言うことが出来る。幽霊は放っておくとどんな被害をもたらすか分からないので、彼女は出来るだけ早い時刻に幽霊を捕まえたい。なので、彼女は頼れる先輩であるあなたに、彼女と幽霊が遭遇できる最も早い時刻とその遭遇場所を求めるプログラムを書いてほしいと思っている。
さあ、彼女を助けて、彼女のありがたい言葉で彷徨える魂を極楽浄土へと導くのだ！
複数のデータセットが与えられる。
各データセットの形式を以下に示す。
H W （グリッドの南北方向のマスの数、グリッドの東西方向のマスの数： 空白区切りの２つの整数）
H × W の文字 （マスの種類：'.', '#', 'A', または 'B'）
pattern （幽霊の行動パタン：文字列）
'A' は少女の初期位置、'B' は幽霊の初期位置を示す。両者の初期位置は、 '.' のマスの上にある。
pattern は '5', '2', '4', '6', '8' から成る文字列で、各文字の意味は以下の通りである：
| '5' | その場に留まる |
| '8' | 北に1マス進む |
| '6' | 東に1マス進む |
| '4' | 西に1マス進む |
| '2' | 南に1マス進む |
例えば、pattern が "8544" の場合、幽霊は「北に1マス進む」「その場に留まる」「西に1マス進む」「西に1マス進む」の行動パタンを繰り返す。
H, W は 1 以上 20 以下であり、pattern の長さは 10 以下である。
H, W がともに 0 のとき、入力は終了する。
もし少女が幽霊と遭遇できるならば、最も早い遭遇時刻と、その遭遇場所の南北方向の座標、東西方向の座標を空白で区切って1行に出力せよ。グリッドの最北西を座標(0, 0)とし、最南東を座標(H-1, W-1) とする。
どのように行動しても絶対に遭遇できない場合は、 "impossible" と出力せよ。
4 7 A#...#B .#.#.#. .#.#.#. ...#... 5 4 7 A#...#B .#.#.#. .#.#.#. ...#... 2 4 7 A#...#B .#.#.#. .#.#.#. ...#... 4 4 7 A#...#B .#.#.#. .#.#.#. ...#... 442668 1 10 A#.......B 55555554 1 10 A#.......B 55555555 0 0
18 0 6 15 3 6 6 0 0 14 0 4 72 0 0 impossible