#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define range(a) a.begin(), a.end()
#define endl "\n"
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
#define MP make_pair
using P = pair<int, int>;
const long long INF = 1LL<<60;
void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }

const int64_t CYCLES_PER_SEC = 2800000000;

struct Timer {
	int64_t start;
	Timer() { reset(); }
	void reset() { start = getCycle(); }
	void plus(double a) { start -= (a * CYCLES_PER_SEC); }
	inline double get() { return (double)(getCycle() - start) / CYCLES_PER_SEC; }
	inline int64_t getCycle() {
		uint32_t low, high;
		__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
		return ((int64_t)low) | ((int64_t)high << 32);
	}
};

Timer timer;

unsigned long xor128() {
	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	unsigned long t = (x^(x << 11));
	x = y;
	y = z;
	z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

// 0以上1未満の小数をとる乱数
static double rand01(){
	double ans = ((xor128() + 0.5)  * (1.0 / 9223372036854775807));
	return ans / 2;
}

int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	timer.reset();
	double TIMELIMIT = 2.8;
	//double ti = timer.get();
	int N, M;
	cin >> N >> M;
	map<int, vector<string>> mp;
	vector<vector<char>> ans(N, vector<char>(20, '.'));
	int nowx = 0, nowy = 0;
	set<int> length;
	FOR(i,0,M){
		string s;
		cin >> s;
		mp[(int)s.size()].push_back(s);
		length.insert((int)s.size());
	}

	for (auto itr = length.begin(); itr != length.end(); itr++){
		FOR(i,0,(int)mp[*itr].size()){
			string s = mp[*itr][i];
			if(nowx >= N-1 && nowy + *itr >= N){
				char c = 'A';
				for(auto x: ans){
					for(auto y: x){
						if(y == '.')	cout << c++;
						else	cout << y;
						if(c == 'I')	c = 'A';
					}
					cout << endl;
				}
				return 0;
			}
			FOR(k,0,(int)s.size()){
				if(nowy >= 20){nowy = 0; nowx++;}
				ans[nowx][nowy++] = s[k];
			}
		}
	}


		return 0;
}


#include<bits/stdc++.h>
using namespace std;


int main(){
  int h,w;
  cin>>h>>w;

  //(i,j)から a[i][j][k]にいける
  vector<vector<vector<pair<int,int>>>>go(h,vector<vector<pair<int,int>>>(w,vector<pair<int,int>>(0)));
  go.push_back(vector<vector<pair<int,int>>>(26,vector<pair<int,int>>(0)));
  pair<int,int>S,G;
  vector<vector<char>>a(h,vector<char>(w));
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>a[i][j];
      if(a[i][j]=='S'){S={i,j};}
      else if(a[i][j]=='G'){G={i,j};}
      else if(a[i][j]!='.'&&a[i][j]!='#'){
        go[i][j].push_back({h,a[i][j]-'a'});
        go[h][a[i][j]-'a'].push_back({i,j});
      }
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(a[i][j]=='#')continue;
      if(i>0&&a[i-1][j]!='#')go[i][j].push_back({i-1,j});
      if(i<h-1&&a[i+1][j]!='#')go[i][j].push_back({i+1,j});
      if(j>0&&a[i][j-1]!='#')go[i][j].push_back({i,j-1});
      if(j<w-1&&a[i][j+1]!='#')go[i][j].push_back({i,j+1});
    }
  }
  //cout<<"ok\n";
  vector<vector<int64_t>>cost(h,vector<int64_t>(w,1e18));
  cost.push_back(vector<int64_t>(26,1e18));
  cost[S.first][S.second]=0;
  deque<pair<int,int>>bfs;
  bfs.push_back(S);
  while(bfs.size()){
    pair<int,int>n=bfs.front();
    bfs.pop_front();
    if(n.first==h){
      for(int i=0,l=go[h][n.second].size();i<l;i++){
        if(cost[go[h][n.second][i].first][go[h][n.second][i].second]>cost[h][n.second]){
          cost[go[h][n.second][i].first][go[h][n.second][i].second]=cost[h][n.second];
          bfs.push_front({go[h][n.second][i].first,go[h][n.second][i].second});
        }
      }
    }else{
      int i=n.first,j=n.second;
      for(int k=0,l=go[i][j].size();k<l;k++){
        if(cost[go[i][j][k].first][go[i][j][k].second]>cost[i][j]+1){
          cost[go[i][j][k].first][go[i][j][k].second]=cost[i][j]+1;
          bfs.push_back({go[i][j][k].first,go[i][j][k].second});
        }
      }
    }
  }
  /*
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++)cout<<cost[i][j]<<' ';
    cout<<'\n';
  }
  */
  cout<<(cost[G.first][G.second]==1e18?-1:cost[G.first][G.second])<<'\n';
}