Magical Tiles

時間制限 : 1 sec, メモリ制限 : 65536 KB
英語版はこちら

不思議なタイル

ある屋敷に不思議な部屋がありました。その部屋の床には次の 5 種類のタイルが、縦に H 枚、横に W 枚、合計 H × W 枚が敷き詰められています。

  • 東向きの矢印が書かれたタイル
  • 西向きの矢印が書かれたタイル
  • 南向きの矢印が書かれたタイル
  • 北向きの矢印が書かれたタイル
  • 何も書かれていないタイル

矢印の書かれたタイルの上に人が乗ると、不思議な力が働いて、矢印が指す方向の隣のタイルに自動的に移動します。移動先のタイルにも矢印が書かれていると、さらにその矢印の指す方向に自動的に移動します。何も書かれていないタイルの上に人が乗っても、人は移動しません。つまり、いったん矢印の書かれたタイルに乗ると、何も書かれてないタイルに到着するまで自動的に移動することができるのです。部屋の入り口は北西の角にあります。

部屋の状態を表す文字列を読み込み、不思議な力によって移動した結果、最後に到着するタイルの位置を出力するプログラムを作成してください。

HW 列からなる入力データは部屋を真上から見たときのタイルの状態を表しており、上、下、左、右が部屋の北、南、西、東にあたります。左上のタイルの座標は X 座標、Y 座標ともに 0 とし、X 座標は左から右に 0 から W-1、Y 座標は上から下に 0 から H-1 とします。 たとえば以下のようなデータが与えられます。

10 10
>>>v..>>>v
...v..^..v
...>>>^..v
.........v
.v<<<<...v
.v...^...v
.v...^<<<<
.v........
.v...^....
.>>>>^....

入力データ中の各文字が示す意味は次のとおりです。

'>' (大なり記号): 東向きの矢印が書かれたタイル
'<' (小なり記号): 西向きの矢印が書かれたタイル
'^' (べき記号) : 北向きの矢印が書かれたタイル
'v' (小文字ブイ): 南向きの矢印が書かれたタイル
'.' (ピリオド) : 何も書かれていないタイル

タイルの配置によっては、人が同じタイルの列をぐるぐる循環してしまったり、2 枚のタイルの間で行ったり来たりしてしまい、どこにも到着しない場合があります。そのような入力が与えられた場合には、LOOP という文字を出力してください。なお、タイルの矢印は、移動によって部屋の外に出てしまう方向を向いていることはありません。

Input

複数のデータセットが与えられます。入力は 0 二つの行で終わります。

各データセットとして、上記のように、1行目に H, W (H, W ≤ 100) が空白区切りで与えられ、続いてタイルの状態を示す 1 行 W 文字、H 行からなる文字列が与えられます。

Output

各データセットについて、最後に到着するタイルの座標 X Y (空白区切り)または、LOOP を1行に出力してください。

Sample Input

10 10
>>>v..>>>v
...v..^..v
>>>>>>^..v
.........v
.v<<<<...v
.v.v.^...v
.v.v.^<<<<
.v.v.....v
.v...^...v
.>>>>^....
6 10
>>>>>>>>>v
.........v
.........v
>>>>v....v
^...v....v
^<<<<<<<<<
0 0

Output for the Sample Input

5 7
LOOP

Source: PC Koshien 2005 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2005
(modified format)
http://www.pref.fukushima.jp/pc-concours/