Let's solve the puzzle by programming.

The numbers n x n are arranged in a grid pattern. Some of the numbers are circled and we will call them the starting point. The rules of the puzzle are as follows:

* Draw one line that goes vertically and horizontally from each starting point (cannot be drawn diagonally).
* Extend the line so that the sum of the numbers passed is the same as the starting number.
* The line must not be branched.
* Lines cannot pass through numbers already drawn (lines must not intersect).
* A line cannot pass through more than one origin.



As shown in the figure below, the goal of the puzzle is to use all the starting points and draw lines on all the numbers.


<image>


Your job is to create a puzzle-solving program. However, in this problem, it is only necessary to determine whether the given puzzle can be solved.



Input

The input consists of multiple datasets. The format of each dataset is as follows:


n
n x n numbers


Indicates a puzzle given a number of n x n, the starting number is given as a negative number.

When n is 0, it indicates the end of input.

It can be assumed that n is 3 or more and 8 or less, numbers other than the starting point are 1 or more and 50 or less, and the starting point is -50 or more and -1 or less. You may also assume the following as the nature of the puzzle being entered:

* Each row and column of a given puzzle has at least one starting point.
* The number of starting points is about 20% to 40% of the total number of numbers (n x n).

Output

For each dataset, print "YES" if the puzzle can be solved, otherwise "NO" on one line.

Example

Input

3
-3 1 1
2 -4 1
2 1 -1
3
-4 1 1
1 1 -6
1 -5 3
4
-8 6 -2 1
2 -7 -2 1
1 -1 1 1
1 1 1 -5
6
2 2 3 -7 3 2
1 -10 1 1 3 2
2 6 5 2 -6 1
3 4 -23 2 2 5
3 3 -6 2 3 7
-7 2 3 2 -5 -13
6
2 2 3 -7 3 2
1 -10 1 1 3 2
2 6 5 2 -6 1
3 4 -23 2 2 5
3 3 -6 2 3 7
-7 2 3 2 -5 -12
0


Output

YES
NO
NO
YES
NO
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	public static final int[][] move_dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	
	public static boolean is_ok(int x, int y, final int n){
		if(x < 0 || x >= n || y < 0 || y >= n){
			return false;
		}else{
			return true;
		}
	}
	
	public static boolean dfs(int deep, final int size, final int n, boolean using[][], int[][] map, int x, int y, int cur, 
			ArrayList<Integer> x_pos, ArrayList<Integer> y_pos, ArrayList<Integer> values, int painted, final int all){
		final int value = values.get(deep);
		
		/*
		System.out.println(deep + " " + n + " " + cur + "/" + value);
		
		System.out.println("---------------------------------------");
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(using[i][j]){
					System.out.print("x ");
				}else{
					System.out.print(map[i][j] + " ");
				}
			}
			System.out.println();
		}
		System.out.println("---------------------------------------");
//		*/
		if(cur > value){
			return false;
		}else if(cur == value){
			if(deep == size - 1 && painted == all){
				return true;
			}else if(deep == size - 1){
				return false;
			}
			
			final int nx = x_pos.get(deep + 1);
			final int ny = y_pos.get(deep + 1);
			
			return dfs(deep + 1, size, n, using, map, nx, ny, 0, x_pos, y_pos, values, painted, all);
		}else{
			for(int[] move : move_dir){
				final int nx = x + move[0];
				final int ny = y + move[1];
				
				if(!is_ok(nx, ny, n)){
					continue;
				}else if(using[ny][nx]){
					continue;
				}
				
				using[ny][nx] = true;
				if(dfs(deep, size, n, using, map, nx, ny, cur + map[ny][nx], x_pos, y_pos, values, painted + 1, all)){
					return true;
				}
				using[ny][nx] = false;
			}
		}
		
		return false;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		while (true) {
			final int n = sc.nextInt();
			
			if(n == 0){
				break;
			}
			
			boolean[][] using = new boolean[n][n];
			int[][] map = new int[n][n];
			ArrayList<Integer> x_pos = new ArrayList<Integer>();
			ArrayList<Integer> y_pos = new ArrayList<Integer>();
			ArrayList<Integer> values = new ArrayList<Integer>();
			
			int count = 0;
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					final int input = sc.nextInt();
					
					if(input < 0){
						using[i][j] = true;
						y_pos.add(i);
						x_pos.add(j);
						values.add(-input);
					}else{
						count++;
						map[i][j] = input;
					}
				}
			}
			
			final int size = x_pos.size();
			
			final boolean ret = dfs(0, size, n, using, map, x_pos.get(0), y_pos.get(0), 0, x_pos, y_pos, values, 0, count);
			
			System.out.println(ret ? "YES" : "NO");
		}

		sc.close();
	}
}