Problem: There is an evil creature in a square on N-by-M grid (2 \leq N, M \leq 100), and you want to kill it using a laser generator located in a different square. Since the location and direction of the laser generator are fixed, you may need to use several mirrors to reflect laser beams. There are some obstacles on the grid and you have a limited number of mirrors. Please find out whether it is possible to kill the creature, and if possible, find the minimum number of mirrors.

There are two types of single-sided mirrors; type P mirrors can be placed at the angle of 45 or 225 degrees from east-west direction, and type Q mirrors can be placed with at the angle of 135 or 315 degrees. For example, four mirrors are located properly, laser go through like the following.

<image>

Note that mirrors are single-sided, and thus back side (the side with cross in the above picture) is not reflective. You have A type P mirrors, and also A type Q mirrors (0 \leq A \leq 10). Although you cannot put mirrors onto the squares with the creature or the laser generator, laser beam can pass through the square. Evil creature is killed if the laser reaches the square it is in.



Input

Each test case consists of several lines.

The first line contains three integers, N, M, and A. Each of the following N lines contains M characters, and represents the grid information. '#', '.', 'S', 'G' indicates obstacle, empty square, the location of the laser generator, and the location of the evil creature, respectively. The first line shows the information in northernmost squares and the last line shows the information in southernmost squares. You can assume that there is exactly one laser generator and exactly one creature, and the laser generator emits laser beam always toward the south.

Output

Output the minimum number of mirrors used if you can kill creature, or -1 otherwise.

Examples

Input

3 3 2
S#.
...
.#G


Output

2


Input

3 3 1
S#.
...
.#G


Output

-1


Input

3 3 1
S#G
...
.#.


Output

2


Input

4 3 2
S..
...
..#
.#G


Output

-1

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

enum DIR{
	North,
	East,
	West,
	South,
};

int H,W,A;
char map[100][101];

struct Data{
	DIR in_dir,out_dir;
	short row,col;
	char mirror;
};

struct Info{
	void set(DIR arg_dir,short arg_row,short arg_col,short arg_rest_P,short arg_rest_Q,short arg_time){
		dir = arg_dir;
		row = arg_row;
		col = arg_col;
		rest_P = arg_rest_P;
		rest_Q = arg_rest_Q;
		time = arg_time;
	}
	DIR dir;
	short row,col,rest_P,rest_Q,time,num_data;
	Data data[21];
};

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1)return true;
	else{
		return false;
	}
}

bool canPut(Data data[21],int num_data,int row,int col){

	if(num_data == 1)return true;

	int start_row,start_col,next_row,next_col;

	for(int i = 1; i < num_data; i++){

		start_row = data[i-1].row;
		start_col = data[i-1].col;
		next_row = data[i].row;
		next_col = data[i].col;

		switch(data[i-1].out_dir){
		case North:
			for(int i = start_row; i >= next_row; i--){
				if(row == i && col == start_col){
					return false;
				}
			}
			break;
		case East:
			for(int i = start_col; i <= next_col; i++){
				if(row == start_row && col == i){
					return false;
				}
			}
			break;
		case West:
			for(int i = start_col; i >= next_col; i--){
				if(row == start_row && col == i){
					return false;
				}
			}
			break;
		case South:
			for(int i = start_row; i <= next_row; i++){
				if(row == i && col == start_col){
					return false;
				}
			}
			break;
		}
	}


	return true;
}

void copyData(Info& to,Info from){
	for(int k = 0; k < from.num_data;k++){
		to.data[k].row = from.data[k].row;
		to.data[k].col = from.data[k].col;
		to.data[k].mirror = from.data[k].mirror;
		to.data[k].in_dir = from.data[k].in_dir;
		to.data[k].out_dir = from.data[k].out_dir;
	}
	to.num_data = from.num_data;
}

int main(){

	Info first;

	scanf("%d %d %d",&H,&W,&A);


	int***** minTime = new int****[H];
	for(int a = 0; a < H; a++){
		minTime[a] = new int***[W];
		for(int b = 0; b < W; b++){
			minTime[a][b]  = new int**[4];
			for(int c = 0; c < 4; c++){
				minTime[a][b][c] = new int*[A+1];
				for(int d = 0; d <= A; d++){
					minTime[a][b][c][d] = new int[A+1];
					for(int e = 0; e <= A; e++)minTime[a][b][c][d][e] = BIG_NUM;
				}
			}
		}
	}

	for(short i = 0; i < H; i++){
		scanf("%s",map[i]);
		for(short k = 0; k < W; k++){
			if(map[i][k] == 'S'){
				first.set(South,i+1,k,A,A,0);
				if(i < H-1)minTime[i+1][k][South][A][A] = 0;
			}
		}
	}

	if(rangeCheck(first.row,first.col) == false || map[first.row][first.col] == '#'){
		printf("-1\n");
		return 0;
	}

	first.data[0].row = first.row-1;
	first.data[0].col = first.col;
	first.data[0].out_dir = South;

	int ans = BIG_NUM;
	first.num_data = 1;

	queue<Info> Q;
	Q.push(first);

	short next_row,next_col;
	char mirror;

	bool FLG;

	while(!Q.empty()){

		if(map[Q.front().row][Q.front().col] == 'G'){
			ans = min(ans,(A-Q.front().rest_P)+(A-Q.front().rest_Q));
			Q.pop();
		}else if(Q.front().time > minTime[Q.front().row][Q.front().col][Q.front().dir][Q.front().rest_P][Q.front().rest_Q]){
			Q.pop();
		}else{

			FLG = true;

			for(int i = 1; i < Q.front().num_data; i++){
				if(Q.front().data[i].row == Q.front().row && Q.front().data[i].col == Q.front().col){
					mirror = Q.front().data[i].mirror;
					FLG = false;
					break;
				}
			}


			if(FLG){
				switch(Q.front().dir){
				case North:

					next_row = Q.front().row-1;
					next_col = Q.front().col;

					if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != '#' &&
							minTime[next_row][next_col][North][Q.front().rest_P][Q.front().rest_Q] > Q.front().time+1){
						minTime[next_row][next_col][North][Q.front().rest_P][Q.front().rest_Q] = Q.front().time+1;
						Info new_info;
						new_info.set(North,next_row,next_col,Q.front().rest_P,Q.front().rest_Q,Q.front().time+1);
						copyData(new_info,Q.front());
						Q.push(new_info);
					}

					next_row = Q.front().row;
					next_col = Q.front().col-1;

					if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != '#' && Q.front().rest_P > 0 && map[Q.front().row][Q.front().col] != 'S' &&
							canPut(Q.front().data,Q.front().num_data,Q.front().row,Q.front().col) == true &&
							 minTime[next_row][next_col][West][Q.front().rest_P-1][Q.front().rest_Q] > Q.front().time+1){
						minTime[next_row][next_col][West][Q.front().rest_P-1][Q.front().rest_Q] = Q.front().time+1;
						Info new_info;
						new_info.set(West,next_row,next_col,Q.front().rest_P-1,Q.front().rest_Q,Q.front().time+1);
						copyData(new_info,Q.front());
						new_info.data[new_info.num_data].row = Q.front().row;
						new_info.data[new_info.num_data].col = Q.front().col;
						new_info.data[new_info.num_data].mirror = 'P';
						new_info.data[new_info.num_data].in_dir = South;
						new_info.data[new_info.num_data].out_dir = West;
						new_info.num_data++;
						Q.push(new_info);
					}

					next_row = Q.front().row;
					next_col = Q.front().col+1;

					if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != '#' && Q.front().rest_Q > 0 && map[Q.front().row][Q.front().col] != 'S' &&
							canPut(Q.front().data,Q.front().num_data,Q.front().row,Q.front().col) == true &&
							minTime[next_row][next_col][East][Q.front().rest_P][Q.front().rest_Q-1] > Q.front().time+1){
						minTime[next_row][next_col][East][Q.front().rest_P][Q.front().rest_Q-1] = Q.front().time+1;
						Info new_info;
						new_info.set(East,next_row,next_col,Q.front().rest_P,Q.front().rest_Q-1,Q.front().time+1);
						copyData(new_info,Q.front());
						new_info.data[new_info.num_data].row = Q.front().row;
						new_info.data[new_info.num_data].col = Q.front().col;
						new_info.data[new_info.num_data].mirror = 'Q';
						new_info.data[new_info.num_data].in_dir = South;
						new_info.data[new_info.num_data].out_dir = East;
						new_info.num_data++;

						Q.push(new_info);
					}

					break;
				case East:

					next_row = Q.front().row;
					next_col = Q.front().col+1;

					if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != '#' &&
							minTime[next_row][next_col][East][Q.front().rest_P][Q.front().rest_Q] > Q.front().time+1){
						minTime[next_row][next_col][East][Q.front().rest_P][Q.front().rest_Q] = Q.front().time+1;
						Info new_info;
						new_info.set(East,next_row,next_col,Q.front().rest_P,Q.front().rest_Q,Q.front().time+1);
						copyData(new_info,Q.front());
						Q.push(new_info);
					}

					next_row = Q.front().row-1;
					next_col = Q.front().col;

					if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != '#' && Q.front().rest_Q > 0 && map[Q.front().row][Q.front().col] != 'S' &&
							canPut(Q.front().data,Q.front().num_data,Q.front().row,Q.front().col) == true &&
							minTime[next_row][next_col][North][Q.front().rest_P][Q.front().rest_Q-1] > Q.front().time+1){
						minTime[next_row][next_col][North][Q.front().rest_P][Q.front().rest_Q-1] = Q.front().time+1;
						Info new_info;
						new_info.set(North,next_row,next_col,Q.front().rest_P,Q.front().rest_Q-1,Q.front().time+1);
						copyData(new_info,Q.front());
						new_info.data[new_info.num_data].row = Q.front().row;
						new_info.data[new_info.num_data].col = Q.front().col;
						new_info.data[new_info.num_data].mirror = 'Q';
						new_info.data[new_info.num_data].in_dir = West;
						new_info.data[new_info.num_data].out_dir = North;
						new_info.num_data++;

						Q.push(new_info);
					}


					next_row = Q.front().row+1;
					next_col = Q.front().col;

					if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != '#' && Q.front().rest_P > 0 && map[Q.front().row][Q.front().col] != 'S' &&
							canPut(Q.front().data,Q.front().num_data,Q.front().row,Q.front().col) == true &&
							minTime[next_row][next_col][South][Q.front().rest_P-1][Q.front().rest_Q] > Q.front().time+1){
						minTime[next_row][next_col][South][Q.front().rest_P-1][Q.front().rest_Q] = Q.front().time+1;
						Info new_info;
						new_info.set(South,next_row,next_col,Q.front().rest_P-1,Q.front().rest_Q,Q.front().time+1);
						copyData(new_info,Q.front());
						new_info.data[new_info.num_data].row = Q.front().row;
						new_info.data[new_info.num_data].col = Q.front().col;
						new_info.data[new_info.num_data].mirror = 'P';
						new_info.data[new_info.num_data].in_dir = West;
						new_info.data[new_info.num_data].out_dir = South;
						new_info.num_data++;
						Q.push(new_info);
					}

					break;
				case West:

					next_row = Q.front().row;
					next_col = Q.front().col-1;

					if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != '#' &&
							minTime[next_row][next_col][West][Q.front().rest_P][Q.front().rest_Q] > Q.front().time+1){
						minTime[next_row][next_col][West][Q.front().rest_P][Q.front().rest_Q] = Q.front().time+1;
						Info new_info;
						new_info.set(West,next_row,next_col,Q.front().rest_P,Q.front().rest_Q,Q.front().time+1);
						copyData(new_info,Q.front());
						Q.push(new_info);
					}

					next_row = Q.front().row-1;
					next_col = Q.front().col;

					if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != '#' && Q.front().rest_P > 0 && map[Q.front().row][Q.front().col] != 'S' &&
							canPut(Q.front().data,Q.front().num_data,Q.front().row,Q.front().col) == true &&
							minTime[next_row][next_col][North][Q.front().rest_P-1][Q.front().rest_Q] > Q.front().time+1){
						minTime[next_row][next_col][North][Q.front().rest_P-1][Q.front().rest_Q] = Q.front().time+1;
						Info new_info;
						new_info.set(North,next_row,next_col,Q.front().rest_P-1,Q.front().rest_Q,Q.front().time+1);
						copyData(new_info,Q.front());
						new_info.data[new_info.num_data].row = Q.front().row;
						new_info.data[new_info.num_data].col = Q.front().col;
						new_info.data[new_info.num_data].mirror = 'P';
						new_info.data[new_info.num_data].in_dir = East;
						new_info.data[new_info.num_data].out_dir = North;
						new_info.num_data++;

						Q.push(new_info);
					}

					next_row = Q.front().row+1;
					next_col = Q.front().col;

					if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != '#' && Q.front().rest_Q > 0 && map[Q.front().row][Q.front().col] != 'S' &&
							canPut(Q.front().data,Q.front().num_data,Q.front().row,Q.front().col) == true &&
							minTime[next_row][next_col][South][Q.front().rest_P][Q.front().rest_Q-1] > Q.front().time+1){
						minTime[next_row][next_col][South][Q.front().rest_P][Q.front().rest_Q-1] = Q.front().time+1;
						Info new_info;
						new_info.set(South,next_row,next_col,Q.front().rest_P,Q.front().rest_Q-1,Q.front().time+1);
						copyData(new_info,Q.front());
						new_info.data[new_info.num_data].row = Q.front().row;
						new_info.data[new_info.num_data].col = Q.front().col;
						new_info.data[new_info.num_data].mirror = 'Q';
						new_info.data[new_info.num_data].in_dir = East;
						new_info.data[new_info.num_data].out_dir = South;
						new_info.num_data++;
						Q.push(new_info);
					}

					break;
				case South:

					next_row = Q.front().row+1;
					next_col = Q.front().col;

					if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != '#' &&
							minTime[next_row][next_col][South][Q.front().rest_P][Q.front().rest_Q] > Q.front().time+1){
						minTime[next_row][next_col][South][Q.front().rest_P][Q.front().rest_Q] = Q.front().time+1;
						Info new_info;
						new_info.set(South,next_row,next_col,Q.front().rest_P,Q.front().rest_Q,Q.front().time+1);
						copyData(new_info,Q.front());
						Q.push(new_info);
					}

					next_row = Q.front().row;
					next_col = Q.front().col+1;

					if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != '#' && Q.front().rest_P > 0 && map[Q.front().row][Q.front().col] != 'S' &&
							canPut(Q.front().data,Q.front().num_data,Q.front().row,Q.front().col) == true &&
							minTime[next_row][next_col][East][Q.front().rest_P-1][Q.front().rest_Q] > Q.front().time+1){
						minTime[next_row][next_col][East][Q.front().rest_P-1][Q.front().rest_Q] = Q.front().time+1;
						Info new_info;
						new_info.set(East,next_row,next_col,Q.front().rest_P-1,Q.front().rest_Q,Q.front().time+1);
						copyData(new_info,Q.front());
						new_info.data[new_info.num_data].row = Q.front().row;
						new_info.data[new_info.num_data].col = Q.front().col;
						new_info.data[new_info.num_data].mirror = 'P';
						new_info.data[new_info.num_data].in_dir = North;
						new_info.data[new_info.num_data].out_dir = East;
						new_info.num_data++;
						Q.push(new_info);
					}

					next_row = Q.front().row;
					next_col = Q.front().col-1;

					if(rangeCheck(next_row,next_col) == true && map[next_row][next_col] != '#' && Q.front().rest_Q > 0 && map[Q.front().row][Q.front().col] != 'S' &&
							canPut(Q.front().data,Q.front().num_data,Q.front().row,Q.front().col) == true &&
							 minTime[next_row][next_col][West][Q.front().rest_P][Q.front().rest_Q-1] > Q.front().time+1){
						minTime[next_row][next_col][West][Q.front().rest_P][Q.front().rest_Q-1] = Q.front().time+1;
						Info new_info;
						new_info.set(West,next_row,next_col,Q.front().rest_P,Q.front().rest_Q-1,Q.front().time+1);
						copyData(new_info,Q.front());
						new_info.data[new_info.num_data].row = Q.front().row;
						new_info.data[new_info.num_data].col = Q.front().col;
						new_info.data[new_info.num_data].mirror = 'Q';
						new_info.data[new_info.num_data].in_dir = North;
						new_info.data[new_info.num_data].out_dir = West;
						new_info.num_data++;
						Q.push(new_info);
					}

					break;
				}


				Q.pop();
			}else{
				Q.pop();
			}
		}
	}


	if(ans == BIG_NUM){
		printf("-1\n");
	}else{
		printf("%d\n",ans);
	}

	return 0;
}