#include<bits/stdc++.h>
using namespace std;
#define ll int
#define inf 1e9
vector<pair<ll,ll> >ad[30];
bool cnt[30];
ll cost[2009][2009];
queue<pair<ll,ll> >q;
char vec[2009][2009];
bool vis[2009][2009];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll a,b,c,d,e,i,j,k,l,n,m,x,y,t,p,xs,ys,xd,yd;
    cin>>n>>m;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            cin>>vec[i][j];
            if(vec[i][j]=='S')
            {
                xs=i;
                ys=j;
            }
            else if(vec[i][j]=='G')
            {
                xd=i;
                yd=j;
            }
            else if(vec[i][j]>='a' && vec[i][j]<='z')
            {
                a=vec[i][j]-'a';
                ad[a].push_back({i,j});
            }
            cost[i][j]=inf;
        }
    }
    cost[xs][ys]=0;
    q.push({xs,ys});
    while(!q.empty())
    {
        a=q.front().first;
        b=q.front().second;
        q.pop();

        x=a+1;
        y=b;
        if((x>=1 && x<=n) && (y>=1 && y<=m) && !vis[x][y] && vec[x][y]!='#')
        {
            vis[x][y]=true;
            cost[x][y]=cost[a][b]+1;
            q.push({x,y});
        }

        x=a-1;
        y=b;
        if((x>=1 && x<=n) && (y>=1 && y<=m) && !vis[x][y] && vec[x][y]!='#')
        {
            vis[x][y]=true;
            cost[x][y]=cost[a][b]+1;
            q.push({x,y});
        }

        x=a;
        y=b+1;
        if((x>=1 && x<=n) && (y>=1 && y<=m) && !vis[x][y] && vec[x][y]!='#')
        {
            vis[x][y]=true;
            cost[x][y]=cost[a][b]+1;
            q.push({x,y});
        }

        x=a;
        y=b-1;
        if((x>=1 && x<=n) && (y>=1 && y<=m) && !vis[x][y] && vec[x][y]!='#')
        {
            vis[x][y]=true;
            cost[x][y]=cost[a][b]+1;
            q.push({x,y});
        }

        if(vec[a][b]>='a' && vec[a][b]<='z')
        {
            x=vec[a][b]-'a';
            if(!cnt[x])
            {
                cnt[x]=true;
                c=cost[a][b];
                l=ad[x].size();
                for(i=0; i<l; i++)
                {
                    a=ad[x][i].first;
                    b=ad[x][i].second;
                    if(!vis[a][b])
                    {
                        vis[a][b]=true;
                        cost[a][b]=c+1;
                        q.push({a,b});
                    }
                }
            }
        }

    }

    if(cost[xd][yd]==inf)
    {
        cost[xd][yd]=-1;
    }

    cout<<cost[xd][yd]<<endl;
}

//#include <atcoder/all>
//using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPR(i, n) for(int i=n-1; i>=0; i--)
#define FOR(i, m, n) for(int i=m; i<n; i++)
#define ALL(v) v.begin(), v.end()
#define bit(n) (1LL<<(n))
#define FIX(d) fixed << setprecision(d)
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1e9;
const ll LINF = (1LL<<60);

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

int n,m,cnt;
vector<string> genome(40, string(40, 'A')), fact(800);

void init(){
  REP(i,n) REP(j,n){
    char c = 'A' + (xor128() % 8);
    genome[i][j] = c;
    genome[i+n][j] = c;
    genome[i][j+n] = c;
  }
}

int countStr(){
  int ret = 0;
  REP(k,m){
    bool found = false;
    REP(i,n){ 
      if(found) break;
      REP(j,n){
        if(genome[i].substr(j, fact[k].size()) == fact[k]){
          ret++;
          found = true;
          break;
        }
      }
    }

    if(found) continue;
    REP(j,n){ 
      if(found) break;
      REP(i,n){
        string tmp;
        FOR(d,i,i+fact[k].size()) tmp.push_back(genome[d][j]);
        if(tmp == fact[k]){
          ret++;
          found = true;
          break;
        }
      }
    }
  }
  return ret;
}

void update1(){
  int ni = xor128() % n;
  int nj = xor128() % n;
  char nc = 'A' + (xor128() % 8);
  char pc = genome[ni][nj];

  genome[ni][nj] = genome[ni+n][nj] = genome[ni][nj+n] = nc;
  int cur_cnt = countStr();
  if(!chmax(cnt, cur_cnt)){
    genome[ni][nj] = genome[ni+n][nj] = genome[ni][nj+n] = pc;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  REP(i,m) cin >> fact[i];
  init();
  cnt = countStr();

  int ti = clock();
  while(clock() - ti < 290 * CLOCKS_PER_SEC / 100){ // 2.9秒で打ち切り
    if(cnt==n) break;
    REP(tk, 100){
      
    }
  }

  REP(i,n) cout << genome[i].substr(n) << '\n';
  return 0;
}
