0969 - 空間移動（亜空間移動）

時間制限 2 秒 / メモリ制限 64 MB / 得点 100 / Writer 珈琲の素材は虚数渦動 / x 2 / 統計 /

TLE
2sec
MLE
64MB
得点
100

問題

作戦中、シュヴィは遠方より近づいてくる天翼種に気がつかなかった。（はやく逃げないと・・・！）エネルギーをあまり消費しないようにするため、高度を変えることなく前後左右の移動により、実際の空間と亜空間を通り、目標地点まで移動することにした。ただし、亜空間内はエネルギー消費が激しいため、継続して e しか移動できない。また相手は魔法により障害物を作っており目標地点まで辿り着けるがどうかわからず、もしかしたら迎撃をしなければいけなくなるかもしれない。そのため、辿り着けるかどうかを判断しなければいけない。


「ご機嫌よう、スクラップ♪ 早速ですが死んでくださいますか？」


「まだ、死ねない、の・・・！」

入力

h w e
m1 1 ・・・ m1 w
:
:
:
mh 1 ・・・ mh w
s1 1 ・・・ s1 w
:
:
:
sh 1 ・・・ sh w

1 行目に地形情報の縦幅を表す整数 h 、横幅を表す整数 w 、亜空間内を継続して移動できる最大数（亜空間内での移動数であり、亜空間への進入及び退出は含めない）を表す整数 e が与えられる。

2 行目以降に実際の空間の地形情報を表す m が与えられる。

  • . : 道
  • # : 障害物（そこを通ることも亜空間から退出してくることもできない）
  • S : 現在地
  • G : 目標地点

その後、亜空間の情報を表す s が与えられる。（縦横幅は実際の空間と同一）

  • . : 通過可能
  • # : 通過不可能（進入・退出も不可能）

出力

目標地点に辿り着けるなら "OK" 、そうでなければ "NG" を出力せよ。なお、一度通ったところをもう一度通ることはできないものとする。出力の最後に改行を入れることを忘れずに。

制約

全ての入出力ケースについて以下を満たす。

  • 2 ≦ h, w ≦ 30
  • 1 ≦ e ≦ 100

入出力例

入力例1

2 2 2
S#
G#
##
##

出力例1

OK

入力例2

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

出力例2

OK

入力例3

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

出力例3

OK

入力例4

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

出力例4

NG

補足

実際の空間の座標と亜空間の座標は対応している。そのため、実際の空間の (0,1) 地点で亜空間に進入する場合、亜空間の (0,1) 地点に移動することになり、逆に亜空間の (0,2) 地点から実際の空間に退出する場合も、実際の空間の (0,2) 地点に移動することになる。