#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

bool check(const vector<string>& grid, int len, int s, int y, int x, bitset<5> push)
{
    int h = grid.size();
    int w = grid[0].size();
    if(!(0 <= y && y < h && 0 <= x && x < w))
        return false;

    if(s == 0){
        if(grid[y][x] == '#' || grid[y][x] == '^' || (islower(grid[y][x]) && !push[grid[y][x]-'a']))
            return false;
    }
    else if(s == 1){
        if(x + len > w)
            return false;
        for(int x2=x; x2<x+len; ++x2){
            if(grid[y][x2] == '#' || (islower(grid[y][x2]) && !push[grid[y][x2]-'a']))
                return false;
        }
    }
    else{
        if(y + len > h)
            return false;
        for(int y2=y; y2<y+len; ++y2){
            if(grid[y2][x] == '#' || (islower(grid[y2][x]) && !push[grid[y2][x]-'a']))
                return false;
        }
    }
    return true;
}

int main()
{
    int h, w, len;
    cin >> h >> w >> len;
    vector<string> grid(h, string(w, ' '));
    int sy, sx, gy, gx;
    for(int y=0; y<h; ++y){
        for(int x=0; x<w; ++x){
            cin >> grid[y][x];
            if(grid[y][x] == 'S'){
                sy = y;
                sx = x;
                grid[y][x] = '.';
            }
            else if(grid[y][x] == 'G'){
                gy = y;
                gx = x;
                grid[y][x] = '.';
            }
        }
    }

    vector<vector<int> > ts = {{1, 1, 2, 2}, {0, 0, 1, 1}, {2, 2, 0, 0}};
    vector<vector<int> > dy = {{0, 0, -len, 1}, {0, 0, -1, 1}, {0, 0, -1, len}};
    vector<vector<int> > dx = {{-len, 1, 0, 0}, {-1, len, 0, 0}, {-1, 1, 0, 0}};

    vector<vector<vector<vector<bool> > > > v(3, vector<vector<vector<bool> > >(h, vector<vector<bool> >(w, vector<bool>(1<<5, false))));
    queue<tuple<int, int, int, int> > q;
    v[0][sy][sx][0] = true;
    q.push(make_tuple(0, sy, sx, 0));

    int ans = -1;
    while(!q.empty()){
        ++ ans;
        int n = q.size();
        while(--n >= 0){
            int s, y, x, push;
            tie(s, y, x, push) = q.front();
            q.pop();
            if(s == 0 && y == gy && x == gx){
                cout << ans << endl;
                return 0;
            }

            for(int i=0; i<4; ++i){
                int s2 = ts[s][i];
                int y2 = y + dy[s][i];
                int x2 = x + dx[s][i];
                int push2 = push;
                if(!check(grid, len, s2, y2, x2, push))
                    continue;

                if(s2 == 0 && isupper(grid[y2][x2]))
                    push2 ^= (1 << (grid[y2][x2] - 'A'));

                if(!v[s2][y2][x2][push2]){
                    v[s2][y2][x2][push2] = true;
                    q.push(make_tuple(s2, y2, x2, push2));
                }
            }
        }
    }

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

Measured memory_bytes: 1428