004 - 配達業者

問題

あなたは配達業者です。なるべく早く荷物を届けなければなりません。指示された移動回数以下で荷物を届けられるかを調べるプログラムを組んでください。

配達をする町は南北にH、東西にWに区切られています。 配達する荷物はN種類あり、それぞれ移動回数Mが指定されます。 スタート地点はSで、お届け先はPで示されます。 それぞれの荷物について、M以下で届けることができる場合はOK、できない場合はNGと出力してください。

入力

  H W
  C1,1 C2,1・・・CW,1
  C1,2 C2,2・・・CW,2
  ・
  ・
  ・
  C1,H C2,H・・・CW,H
  N
  M1
  M2
  ・
  ・
  MN

１行目にH Wが空白区切りで与えられます。

2〜H+1行目に町情報が与えられます。

P ・・・ お届け先

S ・・・ スタート地点

. ・・・ 道路

# ・・・ 建物

移動することができるのは道路上だけです。縦方向・横方向には移動できますが、斜めには移動できません。お届け先への経路は必ず存在します。

次の行に荷物の種類Nが与えられます。

続くN行に移動回数Mが与えられます。

出力

移動回数Mが与えられるごとに、その結果をそれぞれ１行で出力せよ。

制約

1≦H,W≦50

1≦N≦20

1≦M≦200

入出力例

入力例１

3 3
S..
...
..P
3
10
1
4

出力例１

OK
NG
OK

入力例２

5 4
#...
..P#
.#.#
..##
..S.
4
7
3
5
10

出力例２

OK
NG
NG
OK