Problem: Problem

Rolling Block is a game in which a rectangular parallelepiped metal body is rotated and moved, and dropped into a hole in the goal.
The condition to clear this game is to drop the metal body to the goal.

image0

About blocks
From (1) in the figure below, the block is a 1 × 1 × L rectangular parallelepiped. The block can move while rotating in either the north, south, east, or west direction. However, the block cannot move beyond the stage.
From (2) in the figure below, when the block is tilted sideways, it moves while rotating in this way with respect to the moving direction.
From (3) in the figure below, when the block is upright, it moves while rotating in this way with respect to the moving direction.
For (2) and (3), the gray block is the block before movement and the white block is the block after movement.
The black arrow indicates that the block has moved in that direction. Also, the white arrow indicates that the block rotated in that direction as it moved. Dotted lines are drawn on the blocks, which are drawn to make the rotation easier to understand. (Such a dotted line is not written on the blocks actually handled in the game)
image1
The figure below is a diagram to supplement the rotation of the block. Suppose there is a block like a dice where the sum of the faces is 7. The figure below shows the changes in the numbers on the top surface when this block is moved while rotating in four directions, north, south, east, and west, for the upright block and the collapsed block. (Such numbers are not written on the blocks actually handled in the game.)
image2

About the stage
Stages are given in an H × W two-dimensional grid (1 ≤ H, W ≤ 25). Each two-dimensional grid consists of the following types of cells.

* "." Floor
Blocks can sit on the floor.

* "#" wall
It is impossible to proceed to the wall, and it is not possible to move such that a part of the block rides on the wall.

* Initial position of "S" block
Only one character is given for the block. In the initial state, there is only an upright state.

* "G" goal point
Only one goal will appear during the stage.
Also, it is only possible to reach the goal when the block is upright.


* Special walls and switches
Alphabet lowercase special wall
Uppercase alphabet Switch for special walls

The special wall cannot progress when it appears, and it is not possible to move a part of the block so that it rides on the special wall. When the block rotates and stands upright and there is a switch beneath the block, that switch is pressed.
When the switch is pressed, it disappears when a special wall of the same alphabet appears, and conversely it appears when it disappears.
It is assumed that all special walls have appeared immediately after the start of the stage.
There are a maximum of 5 types of special walls and switches that appear on one stage.
The alphabet for the switch is {'A','B','C','D','E'}.
The alphabet for special walls is {'a','b','c','d','e'}.
The number of switches and special walls is H x W or less.
A switch with the same alphabet as the special wall does not always appear on the stage.
Also, a special wall with the same alphabet as the switch does not always appear on the stage.


* "^" Trap
Do not ride the rectangular parallelepiped upright on the trap square.




Given the stage information and the initial position of the metal body, find the shortest effort to solve this puzzle. Output -1 if no solution exists.

Constraints

The input satisfies the following conditions.

* 1 ≤ H, W ≤ 25
* 1 <L <10
* Cell is Cell = {'A','B','C','D','E','S','G','a','b','c','d', It consists of'e','^','#','.'}.

Input


H W L
Cell1-1 ... Cell1-W
..
..
..
CellH-1 ... CellH-W


First, H, W, L are given.
The vertical length, horizontal length, and block length of the stage are shown, respectively.
Next, an H × W two-dimensional grid is given. This represents stage information.

Output

Given the stage information and the initial position of the metal body, find the shortest effort to solve this puzzle.
Output -1 if no solution exists.

Examples

Input

5 5 2
#####
#S.G#
#...#
#...#
#####


Output

4


Input

5 5 2

S.G#
...#
...#


Output

4


Input

3 12 2

S..A..a..G#


Output

6


Input

3 12 2

S...A.a..G#


Output

-1


Input

7 13 3

S....#.....#
.....#.....#
.....#.....#
...........#
..........G#


Output

8


Input

3 12 2

S^^.^^.^^G#


Output

6

Solution (in CPP):

Solution:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <numeric>
using namespace std;
  
struct state {
    int x, y, d, wall;
    state(int x, int y, int d, int w):x(x), y(y), d(d), wall(w) {}
};
 
int h, w, l;
const int MAX = 25;
string board[MAX];
 
const int MAX_D = 3;
const int MAX_WALL = (1 << 5);
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
 
int sx, sy, gx, gy;
int label[MAX][MAX][MAX_D][MAX_WALL];
bool visited[MAX][MAX][MAX_D][MAX_WALL];
 
inline bool valid(int x, int y) {
    return 0 <= x && x < w && 0 <= y && y < h;
}
 
inline bool special_wall(int x, int y, int wall) {
    if(board[y][x] < 'a' || board[y][x] > 'e')
        return false;
 
    return !(wall & (1 << (board[y][x] - 'a')));
}
 
bool check(int ax, int ay, int bx, int by, int w) {
    if(!valid(ax, ay) || !valid(bx, by))
        return false;
 
    for(int i = ay; i <= by; ++i) {
        for(int j = ax; j <= bx; ++j) {
            if(board[i][j] == '#' || special_wall(j, i, w)) return false;
        }
    }
 
    return true;
}
 
inline void change(int& ax, int& ay, int& bx, int& by) {
    if(ax > bx) swap(ax, bx);
    if(ay > by) swap(ay, by);
}
 
int bfs() {
	queue<state> que;
	que.push(state(sx, sy, 0, 0));
 
    memset(label, -1, sizeof(label));
    memset(visited, false, sizeof(visited));
     
    label[sy][sx][0][0] = 0;
    while(!que.empty()) {
        const state s = que.front();
        que.pop();

        if (visited[s.y][s.x][s.d][s.wall]) continue;
        visited[s.y][s.x][s.d][s.wall] = true;
 
        if(s.x == gx && s.y == gy && s.d == 0) return label[s.y][s.x][s.d][s.wall];
		
		const int nl = label[s.y][s.x][s.d][s.wall] + 1;
        switch(s.d) {
        case 0:
        {
            for(int i = 0; i < 4; ++i) {
                int ax = s.x + dx[i];
                int ay = s.y + dy[i];
                int bx = s.x + dx[i] * l;
                int by = s.y + dy[i] * l;
                change(ax, ay, bx, by);
                if(check(ax, ay, bx, by, s.wall)) {
					const int next_dist = (i & 1) + 1;
                    if(label[ay][ax][next_dist][s.wall] != -1) continue;
                    label[ay][ax][next_dist][s.wall] = nl;
                    que.push(state(ax, ay, next_dist, s.wall));
                }
            }
            break;
        }
        case 1:
        {
            for(int i = 1; i <= 3; i += 2) {
                int ax = s.x;
                int ay = s.y + dy[i];
                int bx = s.x + l - 1;
                int by = ay;
                change(ax, ay, bx, by);
                if(check(ax, ay, bx, by, s.wall)) {
                    if(label[ay][ax][1][s.wall] != -1) continue;
                    label[ay][ax][1][s.wall] = nl;
                    que.push(state(ax, ay, 1, s.wall));
                }
            }
 
            int nx = s.x - 1;
            const int ny = s.y;
            int nwall = s.wall;
            if(check(nx, ny, nx, ny, nwall)) {
                if(board[ny][nx] != '^') {
                    if('A' <= board[ny][nx] && board[ny][nx] <= 'E') {
                        nwall |= (1 << (board[ny][nx] - 'A'));
                    }
                    if (label[ny][nx][0][nwall] == -1) {
                        label[ny][nx][0][nwall] = nl;
                        que.push(state(nx, ny, 0, nwall));
                    }
                }
            }
 
            nx = s.x + l;
            nwall = s.wall;
            if(check(nx, ny, nx, ny, nwall)) {
                if(board[ny][nx] != '^') {
                    if('A' <= board[ny][nx] && board[ny][nx] <= 'E') {
                        nwall |= (1 << (board[ny][nx] - 'A'));
                    }
                    if (label[ny][nx][0][nwall] == -1) {
                        label[ny][nx][0][nwall] = nl;
                        que.push(state(nx, ny, 0, nwall));
                    }
                }
            }
            break;
        }
        case 2:
        {
            for(int i = 0; i <= 2; i += 2) {
                const int ax = s.x + dx[i];
                const int ay = s.y;
                const int bx = ax;
                const int by = s.y + l - 1;

                if(check(ax, ay, bx, by, s.wall)) {
                    if (label[ay][ax][2][s.wall] != -1) continue;
                    label[ay][ax][2][s.wall] = nl;
                    que.push(state(ax, ay, 2, s.wall));
                }
            }
 
            const int nx = s.x;
            int ny = s.y - 1;
            int nwall = s.wall;
            if(check(nx, ny, nx, ny, nwall)) {
                if(board[ny][nx] != '^') {
                    if('A' <= board[ny][nx] && board[ny][nx] <= 'E') {
                        nwall |= (1 << (board[ny][nx] - 'A'));
                    }
                    if (label[ny][nx][0][nwall] == -1) {
                        label[ny][nx][0][nwall] = nl;
                        que.push(state(nx, ny, 0, nwall));
                    }
                }
            }
 
            ny = s.y + l;
            nwall = s.wall;
            if(check(nx, ny, nx, ny, nwall)) {
                if(board[ny][nx] != '^') {
                    if('A' <= board[ny][nx] && board[ny][nx] <= 'E') {
                        nwall |= (1 << (board[ny][nx] - 'A'));
                    }
                    if (label[ny][nx][0][nwall] == -1) {
                        label[ny][nx][0][nwall] = nl;
                        que.push(state(nx, ny, 0, nwall));
                    }
                }
            }
            break;
        }
        }
    }
 
    return -1;
}
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

    cin >> h >> w >> l;

	for(int i = 0; i < h; ++i) {
        cin >> board[i];
	}

	for(int i = 0; i < h; ++i) {
		for(int j = 0; j < w; ++j) {
            if (board[i][j] == 'S') {
				sy = i;
				sx = j;
                board[i][j] = '.';
            } else if (board[i][j] == 'G') {
				gy = i;
				gx = j;
                board[i][j] = '.';
            }
        }
    }
 
    cout << bfs() << endl;
 
    return 0;
}