0793 - 配達業者

時間制限 1 秒 / メモリ制限 64 MB / 得点 1 / Writer ei1541 / x 24 / 統計 /

    タグ:

TLE
1sec
MLE
64MB
得点
1

問題

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

配達をする町は南北に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

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

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

    P ・・・ お届け先

    S ・・・ スタート地点

    . ・・・ 道路

    # ・・・ 建物

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

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

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

出力

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

制約

1≦H,W≦50

1≦N≦20

1≦M≦200

入出力例

入力例1

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

出力例1

OK
NG
OK

入力例2

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

出力例2

OK
NG
NG
OK