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:
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
const char *body = "Sabcde";
char s[10][11];
bool vis[10][10][1<<8][10];
bool bad[10][10];

int main() {
	int H, W, N;
	scanf("%d%d%d", &H, &W, &N);
	rep(i, H) scanf("%s", s[i]);
	int inithist = 0, sy = -1, sx = -1;
	rep(i, H) rep(j, W) if(s[i][j] == 'S') {
		int y = i, x = j;
		rep(k, 4) {
			rep(d, 4) {
				int yy = y + dy[d], xx = x + dx[d];
				if(yy<0||yy>=H||xx<0||xx>=W) continue;
				if(s[yy][xx] != body[k+1]) continue;
				y = yy, x = xx;
				inithist |= d << (k * 2);
				break;
			}
		}
		sy = i, sx = j;
//		cerr << sy << ", " << sx << endl;
	}

	int t = 0;
	mset(vis, 0);
	mset(bad, 0);
	vector<int> q, next;
	vis[sy][sx][inithist][0] = true;
	next.pb(inithist | (sy << 8) | (sx << 12) | (0 << 16));
	while(!next.empty()) {
		q.swap(next);
		while(!q.empty()) {
			int ss = q.back(); q.pop_back();
			int hist = ss & 255;
			int y = ss >> 8 & 15, x = ss >> 12 & 15;
			int num = ss >> 16;
//			cerr << y << ", " << x << ", " << hist << ", " << num << ": " << t << endl;
			if(num == N) {
				printf("%d\n", t);
				return 0;
			}
			{	int yy = y, xx = x;
				rep(k, 4) {
					int d = hist >> (k*2) & 3;
					yy += dy[d], xx += dx[d];
					bad[yy][xx] = true;
				}
			}
			rep(d, 4) {
				int yy = y + dy[d], xx = x + dx[d];
				if(yy<0||yy>=H||xx<0||xx>=W) continue;
				if(s[yy][xx] == '#' || bad[yy][xx]) continue;
#define NEXT(y, x, h, n)\
	if(!vis[y][x][h][n]) {\
		next.pb(h | (y << 8) | (x << 12) | (n << 16));\
		vis[y][x][h][n] = true;\
	}
				int newhist = ((hist << 2) & ~(3 << 8)) | (d ^ 2);
				NEXT(yy, xx, newhist, (num + (s[yy][xx] == '1' + num)));
			}
			{	int yy = y, xx = x;
				rep(k, 4) {
					int d = hist >> (k*2) & 3;
					yy += dy[d], xx += dx[d];
					bad[yy][xx] = false;
				}
			}
		}
		t ++;
	}
	puts("-1");
	return 0;
}