Problem I: Rolling Block

Problem

Rolling Blockは直方体の金属体を回転させつつ移動させ、ゴールの穴に落とすゲームである。
このゲームのクリア条件は金属体をゴールに落とすことである。

ブロックについて
下の図の(1)より、ブロックは1×1×Lの直方体である。 ブロックは東西南北のどれかの方向に回転しながら移動することができる。 しかし、ブロックはステージからはみ出るような動きをとることは出来ない。
下の図の(2)より、ブロックが横に倒れている場合は移動方向に対してこのような回転をしつつ移動する。
下の図の(3)より、ブロックが直立している場合は移動方向に対してこのような回転をしつつ移動する。
(2) 、(3) については灰色のブロックが移動前、白色のブロックが移動後のブロックとする。
黒い矢印はその方向に対してブロックが移動したことを示す。 また、白の矢印は移動する際にブロックがその方向へ回転したことを示す。 ブロックに点線が引かれているが、これは回転を分かりやすくするために引いたものである。 （実際にゲームで扱うブロックにはこのような点線は書かれていない）

以下の図はブロックの回転を補足するための図である。 サイコロのように対面の和が7になるようなブロックがあるとする。 直立している場合と倒れているブロックについて、このブロックを東西南北の4方向へ回転しつつ移動させたときの上面の数字の変化を以下の図に示す。 （実際にゲームで扱うブロックにはこのような数字は書かれていない。）

ステージについて
ステージはH×Wの二次元グリッドで与えられる(1 ≤ H,W ≤ 25) 。 二次元グリッドはそれぞれ以下の種類のセルから成る。

• "." 床
  床の上にブロックが乗ることができる。

• "#" 壁
  壁には進行不可能であり、ブロックの一部が壁の上に乗るような移動はできない。

• "S" ブロックの初期位置
  ブロックは１文字だけ与えられる。初期状態では直立している状態しか存在しない。

• "G" ゴール地点
  ゴールはステージ中に１つしか出現しない。
  また、ブロックが直立している状態でしかゴールすることは不可能である。
  

• 特殊壁とスイッチ
  アルファベット小文字 特殊壁
  アルファベット大文字 特殊壁に対応するスイッチ
  
  特殊壁は出現時には進行不可能であり、ブロックの一部が特殊壁の上に乗るような移動はできない。 ブロックが回転を行い直立したときにブロックの真下にスイッチがあるとき、そのスイッチは押される。
  スイッチを押したとき、同じアルファベットの特殊壁が出現しているときは消滅し、逆に消滅しているときは出現する。
  ステージ開始直後ではすべての特殊壁が出現しているとする。
  ひとつのステージで現れる特殊壁とスイッチは最大５種類とする。
  スイッチを表すアルファベットは{'A','B','C','D','E'}である。
  特殊壁を表すアルファベットは{'a','b','c','d','e'}である。
  スイッチと特殊壁の数はH×W個以下である。
  特殊壁と同じアルファベットのスイッチがステージの中に必ず出現するとは限らない。
  また、スイッチと同じアルファベットの特殊壁がステージの中に必ず出現するとは限らない。
  

• "^" トラップ
  トラップのマスの上には直方体が直立した状態で乗ってはいけない。

ステージの情報と金属体の初期位置が与えられるので、このパズルを解く最短手数を求めよ。 解が存在しない場合は-1を出力しなさい。

Input

H W  L
Cell1-1 ... Cell1-W
.
.
.
CellH-1 ... CellH-W

最初にH,W,Lが与えられる。
それぞれ、ステージの縦の長さ、横の長さ、ブロックの長さを示す。
次にH×Wの二次元グリッドが与えられる。これはステージの情報を表している。

Constraints

入力は以下の条件を満たす。

• 1 ≤ H,W ≤ 25
• 1 < L < 10
• Cell は Cell = {'A','B','C','D','E','S','G','a','b','c','d','e','^','#','.'} から成る。

Output

ステージの情報と金属体の初期位置が与えられるので、このパズルを解く最短手数を求めよ。
解が存在しない場合は-1を出力しなさい。

Sample Input 1

5 5 2
#####
#S.G#
#...#
#...#
#####

Sample Output 1

4

Sample Input 2

3 12 2
############
#S..A..a..G#
############

Sample Output 2

6

Sample Input 3

3 12 2
############
#S...A.a..G#
############

Sample Output 3

-1

Sample Input 4

7 13 3
#############
#S....#.....#
#.....#.....#
#.....#.....#
#...........#
#..........G#
#############

Sample Output 4

8

Sample Input 5

3 12 2
############
#S^^.^^.^^G#
############

Sample Output 5

6