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 JAVA):

Solution:
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

	public static final int BIG_NUM = 2000000000;
	public static final int MOD = 1000000007;
	public static final long HUGE_NUM = 99999999999999999L;
	public static final double EPS = 0.000000001;

	public static final int OK = 0;
	public static final int NOT = 1;
	public static final int UNDEFINED = 2;
	public static final int SIZE = 255;
	public static int table[];
	public static int min_dist1[],min_dist2[];
	public static int MAX;
	public static int N;

	@SuppressWarnings("unchecked")
	public static void main(String[] args) {

		//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Scanner scanner = new Scanner(System.in);

		table = new int[SIZE];
		min_dist1 = new int[SIZE];
		min_dist2 = new int[SIZE];

		StringBuilder ans = new StringBuilder();

		while(true){

			MAX = scanner.nextInt();
			if(MAX == 0)break;

			N = scanner.nextInt();

			for(int i = 1; i <= N; i++){

				table[i] = scanner.nextInt();
			}

			min_dist1[0] = 0;

			for(int i = 1; i <= N; i++){

				min_dist1[i] = BIG_NUM;
			}

			PriorityQueue<Info> Q = new PriorityQueue<Info>();

			//startから行けるセルを調べる

			for(int i = 1; i <= MAX; i++){

				int loc = i;
				if(loc >= N+1){

					continue;
				}

				loc += table[i];
				if(loc >= N+1){

					continue;
				}else if(loc <= 0){

					continue;
				}

				min_dist1[loc] = 1;
				Q.add(new Info(loc,1));
			}

			while(!Q.isEmpty()){

				if(Q.peek().sum_dist > min_dist1[Q.peek().node_id]){

					Q.poll();

				}else{

					for(int k = 1; k <= MAX; k++){

						int loc = Q.peek().node_id+k;
						if(loc >= N+1)continue;

						loc += table[loc];

						if(loc >= N+1 || loc <= 0)continue;

						if(min_dist1[loc] > Q.peek().sum_dist+1){
							min_dist1[loc] = Q.peek().sum_dist+1;
							Q.add(new Info(loc,min_dist1[loc]));
						}
					}

					Q.poll();
				}
			}

			boolean FLG = true;

			for(int i = 0; i <= N; i++){
				if(min_dist1[i] == BIG_NUM)continue;

				for(int k = 0; k <= N+1; k++){

					min_dist2[k] = BIG_NUM;
				}

				min_dist2[i] = 0;
				Q.add(new Info(i,0));

				while(!Q.isEmpty()){

					if(Q.peek().sum_dist > min_dist2[Q.peek().node_id]){

						Q.poll();

					}else{

						for(int k = 1; k <= MAX; k++){

							int loc = Q.peek().node_id+k;
							if(loc >= N+1){

								min_dist2[N+1] = Q.peek().node_id+1;
								break;
							}

							loc += table[loc];

							if(loc >= N+1){

								min_dist2[N+1] = Q.peek().node_id+1;
								break;
							}else if(loc <= 0){

								loc = 0;
							}


							if(min_dist2[loc] > Q.peek().sum_dist+1){
								min_dist2[loc] = Q.peek().sum_dist+1;
								Q.add(new Info(loc,min_dist2[loc]));
							}
						}
						if(min_dist2[N+1] != BIG_NUM){

							break;
						}

						Q.poll();
					}
				}

				while(!Q.isEmpty())Q.poll();

				if(min_dist2[N+1] == BIG_NUM){
					FLG = false;
					break;
				}
			}

			if(FLG){

				ans.append("OK\n");
			}else{

				ans.append("NG\n");
			}
		}
		System.out.print(ans.toString());
	}
}

class Info implements Comparable<Info>{
	public int node_id;
	public int sum_dist;

	Info(int arg_node_id,int arg_sum_dist){
		this.node_id = arg_node_id;
		this.sum_dist = arg_sum_dist;
	}

	public int compareTo(Info arg){
		if(this.sum_dist < arg.sum_dist)return -1;
		if(this.sum_dist > arg.sum_dist)return 1;
		return 0;
	}
}

class UTIL{

	//最大公約数
	public static long gcd(long x,long y){

		x = Math.abs(x);
		y = Math.abs(y);

		if(x < y){

			long tmp = y;
			y = x;
			x = tmp;
		}

		if(y == 0){

			return x;
		}else{

			return gcd(y,x%y);
		}
	}

	//最小公倍数
	public static long lcm(long x,long y){

		return (x*y)/gcd(x,y);
	}

	//String→intへ変換
    public static int getNUM(String tmp_str){

        return Integer.parseInt(tmp_str);
    }

    //文字が半角数字か判定する関数
    public static boolean isNumber(String tmp_str){

        if(tmp_str == null || tmp_str.length() == 0){

            return false;
        }

        Pattern pattern = Pattern.compile("\\A[0-9]+\\z");
        Matcher matcher = pattern.matcher(tmp_str);
        return matcher.matches();
    }
}