Taro made a sugoroku so that everyone can play at the children's association event. In order to make the game interesting, I wrote instructions such as "advance 6" and "back 5" in some of the sugoroku squares other than "Furidashi" and "Agari". Turn the roulette wheel to advance as many times as you can, and if an instruction is written on the stopped square, move according to that instruction. However, it does not follow the instructions of the squares that proceeded according to the instructions.

Roulette shall be able to give a number between 1 and a certain number with equal probability. Also, if you get a larger number than you reach "Agari", or if you follow the instructions and you go beyond "Agari", you will move to "Agari". If you follow the instructions and return before "Furidashi", you will return to "Furidashi".

<image>


However, depending on the instructions of the roulette wheel and the square, it may not be possible to reach the "rise". For example, let's say you made a sugoroku like the one shown in the figure. If you use a roulette wheel that only gives 1 and 2, you can go to "Agari" if you come out in the order of 1 and 2, but if you get 2 first, you will not be able to reach "Agari" forever no matter what comes out. Taro didn't know that and wrote instructions in various squares.

Therefore, on behalf of Taro, please create a program to determine whether or not you may not be able to reach the "rise" depending on the instructions of the roulette and the square.



input

The input consists of multiple datasets. The end of the input is indicated by a single zero line. Each dataset is given in the following format.


max
n
d1
d2
..
..
..
dn


The first line gives the maximum number of roulette wheels max (2 ≤ max ≤ 250), and the second line gives the number of cells other than "starting" and "rising" n (2 ≤ n ≤ 250). .. The next n lines are given the number di (-n ≤ di ≤ n) that represents the indication for each cell. When di is zero, it means that no instruction is written, when it is a positive number, it means | di | forward instruction, and when it is negative, it means | di | back instruction (where | x | is x). Represents an absolute value). All values ​​entered are integers.

The number of datasets does not exceed 100.

output

The judgment result is output to one line for each data set. Depending on the instructions of the roulette and the square, if it may not be possible to reach the "go up", "NG" is output, otherwise "OK" is output.

Example

Input

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


Output

OK
NG
NG

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
while True:
	m = int(input())
	if not m:
		break
	n = int(input())
	ds = [0] + [int(input()) for _ in range(n)] + [0]
	g = [[] for _ in range(n + 2)]
	rg = [[] for _ in range(n + 2)]
	for i in range(n + 2):
		for j in range(min(n + 1, i + 1), min(n + 1, i + m) + 1):
			j = max(0, min(n + 1, j + ds[j]))
			g[i].append(j)
			rg[j].append(i)

	def go(g, bs, i):
		bs[i] = True
		for j in g[i]:
			if not bs[j]:
				go(g, bs, j)
	bs = [False] * (n + 2)
	rbs = [False] * (n + 2)
	go(g, bs, 0)
	go(rg, rbs, n + 1)
	if any((b and (not rb) for (b, rb) in zip(bs, rbs))):
		print('NG')
	else:
		print('OK')


import queue
while True:
	m = int(input())
	if m == 0:
		break
	n = int(input())
	d = [0] * (n + 2)
	for i in range(1, n + 1):
		d[i] = int(input())
	visited = [False] * (n + 2)
	visited[0] = True
	ok = [False] * (n + 2)
	ok[n + 1] = True
	rev = [[] for _ in range(n + 2)]
	que = queue.LifoQueue()
	que.put(0)
	while not que.empty():
		i = que.get()
		for j in range(1, m + 1):
			if i + j > n + 1:
				break
			k = min(max(i + j + d[i + j], 0), n + 1)
			rev[k].append(i)
			if not visited[k]:
				que.put(k)
				visited[k] = True
	que.put(n + 1)
	while not que.empty():
		i = que.get()
		for j in rev[i]:
			if not ok[j]:
				ok[j] = True
				que.put(j)
	ans = 'OK'
	if not visited[n + 1]:
		ans = 'NG'
	for i in range(n + 1):
		if visited[i] and (not ok[i]):
			ans = 'NG'
	print(ans)


def search(x, visited, edges):
	if visited[x]:
		return
	visited[x] = True
	for to in edges[x]:
		search(to, visited, edges)

def main():
	while True:
		m = int(input())
		if m == 0:
			break
		n = int(input())
		mp = [0] + [int(input()) for _ in range(n)] + [0]
		visited = [False] * (n + 2)
		rev_visited = [False] * (n + 2)
		edges = [[] for _ in range(n + 2)]
		rev_edges = [[] for _ in range(n + 2)]
		for i in range(n + 2):
			for j in range(1, m + 1):
				nex = i + j
				nex = min(nex, n + 1)
				nex += mp[nex]
				nex = min(nex, n + 1)
				nex = max(nex, 0)
				edges[i].append(nex)
				rev_edges[nex].append(i)
		search(0, visited, edges)
		search(n + 1, rev_visited, rev_edges)
		for node in range(n + 1):
			if visited[node] and (not rev_visited[node]):
				print('NG')
				break
		else:
			print('OK')
main()


import sys
input = sys.stdin.readline
from collections import deque

def bfs(adj_list, s):
	q = deque([s])
	visited = [False] * (n + 2)
	visited[s] = True
	while q:
		v = q.popleft()
		for nv in adj_list[v]:
			if not visited[nv]:
				visited[nv] = True
				q.append(nv)
	return visited
while True:
	m = int(input())
	if m == 0:
		break
	n = int(input())
	d = [int(input()) for _ in range(n)]
	adj_list = [[] for _ in range(n + 2)]
	rev_adj_list = [[] for _ in range(n + 2)]
	for i in range(n + 1):
		for j in range(1, m + 1):
			if i + j > n:
				adj_list[i].append(n + 1)
				rev_adj_list[n + 1].append(i)
			else:
				t = min(n + 1, max(i + j + d[i + j - 1], 0))
				adj_list[i].append(t)
				rev_adj_list[t].append(i)
	visited_1 = bfs(adj_list, 0)
	visited_2 = bfs(rev_adj_list, n + 1)
	for i in range(n + 2):
		if visited_1[i] and (not visited_2[i]):
			print('NG')
			break
	else:
		print('OK')


from collections import deque
while 1:
	M = int(input())
	if M == 0:
		break
	N = int(input())
	D = [0] + [int(input()) for i in range(N)] + [0]
	G = [[] for i in range(N + 2)]
	u = [0] * (N + 2)
	que = deque([0])
	u[0] = 1
	while que:
		v = que.popleft()
		for j in range(1, M + 1):
			if D[min(v + j, N + 1)] != 0:
				to = max(min(v + j + D[v + j], N + 1), 0)
			else:
				to = min(v + j, N + 1)
			if not u[to]:
				que.append(to)
				u[to] = 1
			G[to].append(v)
	z = [0] * (N + 2)
	que = deque([N + 1])
	z[N + 1] = 1
	while que:
		v = que.popleft()
		for w in G[v]:
			if z[w]:
				continue
			z[w] = 1
			que.append(w)
	print('OK' if u == z else 'NG')


def reachable(graph, init):
	if init not in graph or graph[init] is None:
		return set()
	(tmp, graph[init]) = (graph[init], None)
	return tmp.union(*[reachable(graph, i) for i in tmp])

def sugoroku(m, d):
	d = [0] + d + [0]
	(start, goal) = (0, len(d) - 1)
	graph_to = {goal: {goal}}
	graph_from = {start: {start}}
	for init in range(len(d) - 1):
		for xi in range(1, 1 + m):
			pos = min(init + xi, goal)
			to = max(start, min(pos + d[pos], goal))
			try:
				graph_to[to].add(init)
			except KeyError:
				graph_to[to] = {init}
			try:
				graph_from[init].add(to)
			except KeyError:
				graph_from[init] = {to}
	unreachable_node = reachable(graph_from, start).difference(reachable(graph_to, goal))
	return 0 == len(unreachable_node)
import sys
f = sys.stdin
while True:
	m = int(f.readline())
	if m == 0:
		break
	d = [int(f.readline()) for _ in range(int(f.readline()))]
	print('OK' if sugoroku(m, d) else 'NG')