パチモンクリーチャー

某国で大人気のゲーム、パチモンクリーチャーが日本でリメイクされて発売されました。 ゲームが大好きなあなたは、 このゲームを何度もプレイするうちにどうしたら最速でクリアできるのか考えるようになりました。しかし、いくら考えても最速の攻略方法がわからなかったあなたは、どれだけ早くゲームをクリアできるかを求めるプログラムを作成することにしました。

ゲームの詳細は以下の通りです。

パチモンクリーチャー(以下、パチクリ)という生物が多く存在する世界がゲームの舞台です。各パチクリは、火属性、氷属性、木属性、土属性、水属性の 5 種類の属性のいずれか１つの属性を持ちます。ゲームの主人公は、ゲーム開始時に好きな属性のパチクリ一匹を冒険のパートナーとして選びます。そのパチクリと共にゴールを目指し、ゴールにいるライバルを倒してパチクリマスターになることがゲームの目的です。

しかし、ライバルを倒すためには全属性のパチクリがいないと勝てないので、途中で全属性のパチクリを捕まえなければなりません。パチクリを捕まえるには属性がカギとなります。火属性のパチクリは氷属性のパチクリを捕まえることができ、同様に、氷属性は木属性、木属性は土属性、土属性は水属性、水属性は火属性を捕まえることができます。属性の関連は以下の図のようになります。

以下の図はゲームが行われるマップの一例を表しています。

主人公はパチクリを一匹もってスタート地点である「S」から出発し、一マスずつ移動しながらゴール地点である「G」を目指します。その途中で、最初に持っているパチクリ以外の 4 つの属性のパチクリを捕まえ、ゴール地点であるマス目に移動するとゲーム終了となります。

主人公は、今いるマス目から、辺を共有する隣のマス目に移動することができ、それを一回の移動と数えます。主人公がパチクリのいるマスに移動した場合、そのパチクリを捕まえられる属性のパチクリを持っていればそのパチクリを捕まえたことになります。そのマスにいるパチクリを捕まえられるかの可否にかかわらず、すべてのマスに何度でも移動することができます。

マップの大きさ(横方向の列数、縦方向の行数)とマップの初期状態を入力とし、初めに選んだパチクリの属性と、それ以外の 4 つの属性のパチクリを捕まえるのにかかる、スタート地点からゴール地点に至る最小移動数を出力するプログラムを作成してください。

Input

複数のデータセットの並びが入力として与えられます。入力の終りはゼロふたつの行で示されます。各データセットは以下の形式で与えられます。

W H
c11c12...c1W
c21c22...c2W
:
cH1cH2...cHW

1 行目にマップの横方向の列数 W と縦方向の行数 H (2 ≤ W, H ≤ 1000) が与えられます。続く H 行にマップの i 行目の情報が与えられます。入力されるマップには各マスの状態が与えられます。 「S」は主人公のスタート地点を、 「G」はゴール地点を、「1」「2」「3」「4」「5」はそこにいるパチクリの属性を( 1:火属性、 2:氷属性、 3:木属性、 4:土属性、 5:水属性 をそれぞれ表します)、 「.(ピリオド) 」は何もないマスをそれぞれ表します。 各属性のパチクリの数はそれぞれ 0 以上 1000 以下とします。

データセットの数は140 を超えません。また、データセットの 80 % について、W, H は100 を超えません。

Output

入力データセットごとに、最初に選んだパチクリの属性と最小移動数を１行に出力します。なお、どのように初めのパチクリを選んでも、どのような経路で移動してもそれら 4 つの属性のパチクリを捕まえることができない場合は NA と出力してください。 また、最小移動数が同じになるような最初のパチクリの選び方が複数ある場合は、属性の数字が小さいものを出力してください。

Sample Input

6 6
S.1..4
3..5..
..4.1.
4....5
.2.32.
5.1..G
3 2
...
S.G
0 0

Output for the Sample Input

2 10
NA

---