Problem: G, a college student living in a certain sky city, has a hornworm, Imotaro. He disciplined Imotaro to eat all the food in order with the shortest number of steps. You, his friend, decided to write a program because he asked me to find out if Imotaro was really disciplined.



Input


H W N
area


Input is given in H + 1 lines. The first line contains three integers H, W, N (2 ≤ H ≤ 10, 2 ≤ W ≤ 10, 1 ≤ N ≤ 9). H is the height of the area, W is the width, and N is the number of foods (at this time, 6 + N ≤ H × W always holds).

In each line from the 2nd line to H + 1st line, ´S´, ´1´, 2´,… ´9´, ´a´, ´b´, ´c´, ´d´, ´e´, A W character string consisting of ´ # ´ and ´.´ is written, and each represents the state of each section of the area. In addition, ´S´, ´a´, ´b´, ´c´, ´d´, ´e´ represent the initial state of the hornworm. There is no food or obstacles so that it is covered with the hornworm in the initial state. In addition, the initial position of the hornworm and the position of the food are guaranteed to be entered correctly.

Output

Output the minimum number of steps when the hornworm eats food in order, or -1 if that is not possible.

Examples

Input

5 8 3
#.......
#.####2#
#.#.3..#
#.######
.1Sabcde


Output

14


Input

5 8 3
.......
.####2#
.#.3..#
.######
.1Sabcde


Output

14


Input

2 6 2
.1.baS
.2.cde


Output

7


Input

2 6 2
.1#baS
.2.cde


Output

-1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

int H,W,N;
char field[51][51];
const int dy[]={-1,0,0,1};
const int dx[]={0,-1,1,0};
pii esas[11];
int d[11][11][11][4][4][4][4][4];

int getAng(int cy,int cx,int ny,int nx){
  if(ny-cy==-1)return 0;
  else if(nx-cx==-1)return 1;
  else if(nx-cx==1)return 2;
  return 3;
}

pii calcNxtPoint(int cy,int cx,int ang){
  return pii(cy+dy[ang],cx+dx[ang]);
}

struct Sit{
  int cost;
  int heady,headx;
  int pos;
  int ary[5];
  pii poses[5];
  Sit(int pos_,int hy,int hx,int a,int b,int c,int d,int e,int cost_){
    pos=pos_;
    heady=hy;
    headx=hx;
    ary[0]=a;
    ary[1]=b;
    ary[2]=c;
    ary[3]=d;
    ary[4]=e;
    cost=cost_;
  }
  Sit(){
    cost=0;
    pos=0;
  }
  void update_ary(){
    for(int i=0;i<5;i++){
      if(i==0)ary[i]=getAng(heady,headx,poses[0].first,poses[0].second);
      else ary[i]=getAng(poses[i-1].first,poses[i-1].second,poses[i].first,poses[i].second);
    }
  }
  bool operator<(const Sit &sit)const{
    return this->cost>sit.cost;
  }
};

int main(){

  cin>>H>>W>>N;
  Sit start_sit;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>field[i][j];
      if(field[i][j]=='S'){
        start_sit.heady=i;
        start_sit.headx=j;
        field[i][j]='.';
      }
      else if(field[i][j]>='a'&&field[i][j]<='e'){
        int pos=field[i][j]-'a';
        start_sit.poses[pos]=pii(i,j);
        field[i][j]='.';
      }
      else if(field[i][j]>='1'&&field[i][j]<='9'){
        int pos=field[i][j]-'1';
        esas[pos]=pii(i,j);
      }
    }
  }
  start_sit.update_ary();
  // dijkstra
  queue<Sit> pq;
  pq.push(start_sit);
  memset(d,0x7f,sizeof(d));
  d[start_sit.pos][start_sit.heady][start_sit.headx][start_sit.ary[0]][start_sit.ary[1]][start_sit.ary[2]][start_sit.ary[3]][start_sit.ary[4]]=0;
  while(pq.size()){
    Sit csit=pq.front();pq.pop();
    const int ccost=csit.cost;
    const int cpos=csit.pos;
    const int chy=csit.heady;
    const int chx=csit.headx;

    if(cpos==N){
      cout<<ccost<<endl;
      return 0;
    }
    
    int cary[5];
    for(int i=0;i<5;i++)
      cary[i]=csit.ary[i];
    pii bodys[5];
    // caryの情報から，頭以外の座標を復元
    for(int i=0;i<5;i++){
      if(i==0)bodys[i]=calcNxtPoint(chy,chx,cary[i]);
      else bodys[i]=calcNxtPoint(bodys[i-1].first,bodys[i-1].second,cary[i]);
    }
    for(int i=0;i<4;i++){
      int nhy=chy+dy[i];
      int nhx=chx+dx[i];
      // 頭が動けるという条件
      if(nhy>=0&&nhx>=0&&nhy<H&&nhx<W&&field[nhy][nhx]!='#'){
        // bodyを次の場所へ動かし、条件を満たすか調べる
        // 頭の座標とbodyの座標が一致してはいけない
        pii nbodys[5];
        nbodys[0]=pii(chy,chx);
        for(int i=1;i<5;i++)nbodys[i]=bodys[i-1];
        bool isHead=false;
        for(int i=0;i<5;i++){
          if(nbodys[i].first==nhy&&nbodys[i].second==nhx)
            isHead=true;
        }
        if(isHead)continue;
        // 頭の座標が大丈夫なら，次は頭に餌があるかどうかを調べる
        int npos=cpos;
        if(esas[cpos]==pii(nhy,nhx))npos++;
        int ncost=ccost+1;
        Sit nsit;
        nsit.pos=npos;
        nsit.heady=nhy;
        nsit.headx=nhx;
        nsit.cost=ncost;
        for(int i=0;i<5;i++)
          nsit.poses[i]=nbodys[i];
        nsit.update_ary();
        int nary[5];
        for(int i=0;i<5;i++)
          nary[i]=nsit.ary[i];
        // ここで、コストを更新できるか調べる
        if(d[npos][nhy][nhx][nary[0]][nary[1]][nary[2]][nary[3]][nary[4]]>ncost){
          d[npos][nhy][nhx][nary[0]][nary[1]][nary[2]][nary[3]][nary[4]]=ncost;
          pq.push(nsit);
        }
      }
    }
  }

  cout<<-1<<endl;
  
  return 0;
}