Problem: 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

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"

typedef int Weight;
struct Edge {
	int src, dst;
	Weight weight;
	Edge(int src, int dst, Weight weight) :
		src(src), dst(dst), weight(weight) { }
};
struct Dscc {
public:

	//belongs,newedges
	pair<vector<vector<int>>, vector<vector<int>>>get(const vector<vector<int>>&edges) {
		nums.resize(edges.size());
		fill(nums.begin(), nums.end(), -1);
		vector<vector<int>>revedges(edges.size());
		for (int i = 0; i < edges.size(); ++i) {
			for (auto j : edges[i]) {
				revedges[j].push_back(i);
			}
		}
		int num = 0;
		for (int i = 0; i < edges.size(); ++i) {
			dfs(i, num, edges);
		}
		vector<int>big(nums.size());
		for (int i = 0; i < nums.size(); ++i) {
			big[nums[i]] = i;
		}
		reverse(big.begin(), big.end());
		unis.resize(edges.size());
		fill(unis.begin(), unis.end(), -1);
		num = 0;
		for (int i = 0; i < big.size(); ++i) {

			dfs2(big[i], num, revedges);
			num++;
		}
		vector<int>nums;
		for (int i = 0; i < unis.size(); ++i) {
			nums.push_back(unis[i]);
		}
		sort(nums.begin(), nums.end());
		nums.erase(unique(nums.begin(), nums.end()), nums.end());


		map<int, int>mp;
		for (int i = 0; i < nums.size(); ++i) {
			mp[nums[i]] = i;
		}
		for (int i = 0; i < unis.size(); ++i) {
			unis[i] = mp[unis[i]];
		}

		vector<vector<int>>belongs(nums.size());
		for (int i = 0; i < unis.size(); ++i) {
			belongs[unis[i]].push_back(i);
		}
		vector<vector<int>>newedges(nums.size());
		for (int i = 0; i < edges.size(); ++i) {
			for (auto j : edges[i]) {
				if (unis[i] != unis[j]) {
					newedges[unis[i]].push_back(unis[j]);
				}
			}
		}
		return make_pair(belongs, newedges);
	}

	//belongs,newedges
	pair<vector<vector<int>>, vector<vector<Edge>>>get(const vector<vector<Edge>>&edges) {
		const int old_node_size = edges.size();
		nums.resize(old_node_size);
		fill(nums.begin(), nums.end(), -1);
		vector<vector<Edge>>revedges(old_node_size);
		for (const auto& e : edges) {
			for (const auto& j : e) {
				revedges[j.dst].push_back(Edge(j.dst, j.src, j.weight));
			}
		}
		int num = 0;
		for (int i = 0; i < old_node_size; ++i) {
			dfs(i, num, edges);
		}
		vector<int>big(old_node_size);
		for (int i = 0; i < old_node_size; ++i) {
			big[nums[i]] = i;
		}
		reverse(big.begin(), big.end());

		unis.resize(old_node_size);
		fill(unis.begin(), unis.end(), -1);

		num = 0;
		for (int i = 0; i < old_node_size; ++i) {
			dfs2(big[i], num, revedges);
			num++;
		}
		vector<int>nums;
		for (int i = 0; i < old_node_size; ++i) {
			nums.push_back(unis[i]);
		}

		sort(nums.begin(), nums.end());
		nums.erase(unique(nums.begin(), nums.end()), nums.end());
		const int new_node_size = nums.size();

		map<int, int>mp;
		for (int i = 0; i < new_node_size; ++i) {
			mp[nums[i]] = i;
		}
		for (int i = 0; i < old_node_size; ++i) {
			unis[i] = mp[unis[i]];
		}

		vector<vector<int>>belongs(new_node_size);
		for (int i = 0; i < old_node_size; ++i) {
			belongs[unis[i]].push_back(i);
		}
		vector<vector<Edge>>newedges(new_node_size);
		for (const auto& e : edges) {
			for (const auto& j : e) {
				if (unis[j.src] != unis[j.dst]) {
					newedges[unis[j.src]].push_back(Edge(unis[j.src], unis[j.dst], j.weight));
				}
			}
		}
		return make_pair(belongs, newedges);
	}
private:
	vector<int>nums;
	vector<int>unis;

	void dfs(const int id, int &num, const vector<vector<int>>&edges) {
		if (nums[id] != -1)return;
		else {
			nums[id] = -2;
			for (auto i : edges[id]) {
				dfs(i, num, edges);
			}
		}
		nums[id] = num++;
		return;
	}
	void dfs2(const int id, const int &num, const vector<vector<int>>&edges) {
		if (unis[id] != -1)return;
		else {
			unis[id] = -2;
			for (auto i : edges[id])
				dfs2(i, num, edges);
		}
		unis[id] = num;
		return;
	}
	void dfs(const int id, int &num, const vector<vector<Edge>>&edges) {
		if (nums[id] != -1)return;
		else {
			nums[id] = -2;
			for (auto i : edges[id]) {
				dfs(i.dst, num, edges);
			}
		}
		nums[id] = num++;
		return;
	}
	void dfs2(const int id, const int &num, const vector<vector<Edge>>&edges) {
		if (unis[id] != -1)return;
		else {
			unis[id] = -2;
			for (auto i : edges[id]) {
				dfs2(i.dst, num, edges);
			}
		}
		unis[id] = num;
		return;
	}

}dscc;
int come[300];
bool dfs(const int now,const vector<vector<int>>&edges, const int goal) {
	if (come[now])return true;
	come[now] = true;
	if (now == goal)return true;
	else {
		if (edges[now].empty())return false;
		for (auto e : edges[now]) {
			if (e == now)assert(false);
			if (!dfs(e, edges, goal))return false;
		}
		return true;
	}
}
int main() {
	while (1) {
		memset(come, false, sizeof(come));
		int amax;
		cin >> amax;
		if (!amax)break;
		int N; cin >> N;
		const int goal = N + 1;
		const int start = 0;
		vector<int>ds(goal+1);
		for (int i = 0; i < N; ++i) {
			cin >> ds[i+1];
		}
		vector<vector<int>>edges(N + 2);
		for (int i = 0; i < N + 1; ++i) {
			for (int j = 1; j <= amax; ++j) {
				int next;
				if (i + j >= goal) {
					next = goal;
				}
				else {
					if (i + j + ds[i + j] >= goal) {
						next = goal;
					}
					else if (i + j + ds[i+j]<0) {
						next = 0;
					}
					else {
						next = i + j + ds[i + j];
					}
				}
				if (find(edges[i].begin(), edges[i].end(), next) == edges[i].end()) {
					edges[i].push_back(next);
				}
				sort(edges[i].begin(), edges[i].end());
			}
		}
		auto p=dscc.get(edges);
		int newstart=-1;
		int newgoal=-1;
		for (int i = 0; i < p.first.size();++i) {
			auto b = p.first[i];
			if (find(b.begin(), b.end(), 0)!=b.end()) {
				newstart = i;
			}
			if (find(b.begin(), b.end(), goal) != b.end()) {
				newgoal= i;
			}
		}
		if (newstart == -1 || newgoal == -1)cout << "ff";
		auto newedges = p.second;
		
		bool ans = dfs(newstart, newedges, newgoal);
		if (ans) {
			cout << "OK" << endl;
		}
		else {
			cout << "NG" << endl;
		}
	}
	return 0;
}