#include<bits/stdc++.h>
using namespace std;
struct state{
  int y,x,dir,bit,cost;
};
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
 
int H,W,L;
int sy,sx;
vector<int> cy[5],cx[5];
 
char t[30][30];
bool visited[30][30][3][(1<<5)];
 
int solve(){
  queue< state > Q;
  visited[sy][sx][0][0]=true;
  Q.push((state){sy,sx,0,0,0});
 
  while(!Q.empty()){
    state s=Q.front();Q.pop();
 
    if(t[s.y][s.x]=='G'&&s.dir==0)return s.cost;
 
    for(int i=0;i<5;i++)
      if(s.bit>>i&1){
    for(int j=0;j<(int)cy[i].size();j++)
      t[cy[i][j]][cx[i][j]]='.';
      }
 
    if(s.dir==0){
      for(int i=0;i<4;i++){
    bool f=true;
    for(int j=1;j<=L;j++){
      if(t[s.y+dy[i]*j][s.x+dx[i]*j]=='#'){
        f=false;
        break;
      }
    }
    if(!f)continue;
 
    int ny=s.y+dy[i]*L;
    if(i==2)ny=s.y+1;
 
    int nx=s.x+dx[i]*L;
    if(i==1)nx=s.x+1;
    int ndir=2;
    if(i==1||i==3)ndir=1;
    if(visited[ny][nx][ndir][s.bit])continue;
    visited[ny][nx][ndir][s.bit]=true;
    Q.push((state){ny,nx,ndir,s.bit,s.cost+1});
      }
 
    }else if(s.dir==1){
      for(int i=0;i<4;i++){
    if(i==0||i==2){
      bool f=true;
      for(int j=0;j<L;j++){
        if(t[s.y+dy[i]][s.x+j]=='#')f=false;
      }
      if(!f)continue;
      int ny=s.y+dy[i];
      int nx=s.x;
      if(visited[ny][nx][s.dir][s.bit])continue;
      visited[ny][nx][s.dir][s.bit]=true;
      Q.push((state){ny,nx,s.dir,s.bit,s.cost+1});
    }else{
 
      int ny=s.y;
      int nx=s.x+dx[i];
      if(i==1)nx=s.x+L;
      if(nx>W)continue;
      if(t[ny][nx]=='^'||t[ny][nx]=='#')continue;
 
      int nbit=s.bit;
      if('A'<=t[ny][nx]&&t[ny][nx]<='E'){
        int id=t[ny][nx]-'A';
        nbit=nbit^(1<<id);
      }
      if(visited[ny][nx][0][nbit])continue;
      visited[ny][nx][0][nbit]=true;
      Q.push((state){ny,nx,0,nbit,s.cost+1});
    }
      }
    }else{
      for(int i=0;i<4;i++){
    if(i==1||i==3){
      bool f=true;
      for(int j=0;j<L;j++){
        if(t[s.y+j][s.x+dx[i]]=='#'){
          f=false;
          break;
        }
      }
      if(!f)continue;
 
      int ny=s.y;
      int nx=s.x+dx[i];
      if(visited[ny][nx][s.dir][s.bit])continue;
      visited[ny][nx][s.dir][s.bit]=true;
      Q.push((state){ny,nx,s.dir,s.bit,s.cost+1});
    }else{
      int ny=s.y+dy[i];
      int nx=s.x;
      if(i==2)ny=s.y+L;
      if(ny>H)continue;
      if(t[ny][nx]=='^'||t[ny][nx]=='#')continue;
 
      int nbit=s.bit;
      if('A'<=t[ny][nx]&&t[ny][nx]<='E'){
        int id=t[ny][nx]-'A';
        nbit=nbit^(1<<id);
      }
      if(visited[ny][nx][0][nbit])continue;
      visited[ny][nx][0][nbit]=true;
      Q.push((state){ny,nx,0,nbit,s.cost+1});
    }
      }
    }
 
    for(int i=0;i<5;i++){
      for(int j=0;j<(int)cy[i].size();j++)
    t[cy[i][j]][cx[i][j]]='#';
    }
  }
 
  return -1;
}
 
int main(){
  for(int i=0;i<30;i++)
    for(int j=0;j<30;j++)
      t[i][j]='#';
 
  cin>>H>>W>>L;
  for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
      cin>>t[i][j];
      if(t[i][j]=='S'){
    sy=i;
    sx=j;
      }
 
      if('a'<=t[i][j]&&t[i][j]<='e'){
    int id=t[i][j]-'a';
    cy[id].push_back(i);
    cx[id].push_back(j);
    t[i][j]='#';
      }
    }
  }
  cout<<solve()<<endl;
  return 0;
}

Measured memory_bytes: 1328