Making Sugoroku

Time Limit : 3 sec, Memory Limit : 65536 KB

すごろくを作る

太郎君は、子供会の催しでみんなで遊べるようにすごろくを作りました。ゲームをおもしろくするために、「ふりだし」と「あがり」以外のすごろくのマスのいくつかに「6つ進む」、「5つ戻る」のように指示を書き込んでいきました。ルーレットを回して出た数だけ進み、止まったマスに指示が書き込んであれば、その指示に従って移動します。ただし、指示に従って進んだ先のマスの指示には従いません。

ルーレットは1からある数までの間の数を等確率で出すことができるものとします。また、「あがり」に達するより大きな数が出たときや、指示に従うと「あがり」より先に進んでしまうときは「あがり」に移動します。指示に従って戻るときに「ふりだし」より前に戻ってしまうときは「ふりだし」に戻ることにします。


ところが、ルーレットとマスの指示によっては「あがり」にたどりつけない場合が出てきてしまいます。たとえば、図のようなすごろくを作ったとしましょう。1と2しか出ないルーレットを使うと、1,2の順に出れば「あがり」に行けますが、はじめに2が出たらその後は何が出ても永久に「あがり」にはたどり着けません。太郎君は、そうとは知らずに調子に乗ってあちこちのマスに指示を書き込んでしまいました。

そこで、太郎君に代わって、ルーレットとマスの指示によっては、「あがり」にたどり着けない場合が生じるかどうか判定するプログラムを作成してください。

入力

入力は複数のデータセットからなる。入力の終わりはゼロ1つの行で示される。各データセットは以下の形式で与えられる。

max
n
d1
d2
.
.
.
dn

1行目にルーレットが出す数の最大値 max (2 ≤ max ≤ 250) が与えられ、2行目に「ふりだし」と「あがり」以外のマスの数 n (2 ≤ n ≤ 250) が与えられる。続く n 行に各マスの指示を表す数 di(-n ≤ di ≤ n) が与えられる。di がゼロのときは指示が書いていないことを、正の数のときは |di| 進む指示を、負の数のときは |di| 戻る指示を表す(ここで、|x| は x の絶対値を表す)。入力される値はすべて整数である。

データセットの数は 100 を超えない。

出力

各データセットごとに判定結果を1行に出力する。ルーレットとマスの指示によっては、「あがり」にたどり着けない場合が生じるときは「NG」、そうでなければ「OK」を出力する。

入力例

3
3
-2
1
0
2
4
2
0
-1
-2
2
2
-2
-2
0

出力例

OK
NG
NG

Source: PC Koshien 2012, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2012
http://www.pref.fukushima.jp/pc-concours /