This problem was going to be Juan's history lesson about the 1997 IOI in South Africa. However, the lesson was censored by the rest of the committee, and so the following statement has reached you:

Abraham is a brave explorer who goes where no programmer has gone before. On his next expedition, he plans to investigate a very curious maze. He knows the maze is an $n \times n$ grid with an arrow in every cell. Each arrow points in one of four possible directions: up, down, left or right. If Abraham steps onto a cell, he is forced to follow the arrows starting from that cell. Each arrow moves Abraham one cell in the direction it points; if he reaches an arrow pointing out of the maze, he can escape.

Abraham does not know how the maze's arrows are oriented, but he has other information. On his map of the maze, some cells are coloured black and others white. He believes that if he starts on any black cell, he can never escape the maze, while if he starts on any white cell, he will eventually escape.

Abraham's assumption may be wrong: there are arrangements of black and white cells for which the specified conditions cannot hold for all cells simultaneously, regardless of how the arrows are oriented. The following image shows an example.

The map represents a maze in which the white cells can satisfy Abraham's assumption. If he starts on either of them, the arrows shown lead him out of the maze, but it is impossible for him to remain trapped when starting on a black cell, regardless of how we orient the arrows not shown.

Abraham asks you to help him determine whether, for a given colouring of the cells on his map, there is an arrangement of arrows consistent with his belief for every cell of the grid, both black and white.

Input

• The first line contains a positive integer $n$.
• Each of the next $n$ lines contains $n$ characters, each either 0 or 1. 0 denotes a black cell and 1 a white cell. These $n$ lines describe the grid.

Output

Print SI if the arrows can be oriented so that Abraham can never escape when starting on a black cell, and eventually escapes when starting on a white cell.

Print NO if this is impossible.

Examples

Input 1

3
001
001
111

Output 1

SI

Input 2

2
01
10

Output 2

NO

Note

The first example corresponds to the following colouring (shown on the left), together with a possible arrangement of arrow directions:

The second example was mentioned in the problem's story as a case in which the requested conditions cannot be satisfied for all cells simultaneously.

Constraints

• $2 \le n \le 1000$.

Subtasks

• Subtask 1 (10 points): $n=2$.
• Subtask 2 (25 points): The black cells are guaranteed to form a connected region, and at least two corners of the maze are black.
• Subtask 3 (25 points): The white cells are guaranteed to form a connected region, and fewer than $4n-4$ cells are black.
• Subtask 4 (40 points): No additional constraints.

Note

A set of cells forms a connected region if there is a path between every pair of its cells, moving between cells that share an edge, that only passes through cells of the set. In particular, the black cells form a connected region if there is a path consisting only of black cells between every pair of black cells. Similarly, the white cells form a connected region if there is a path consisting only of white cells between every pair of white cells.

In the first example, both the white cells and the black cells form a connected region.

In the second example, the black cells do not form a connected region because any path between them also passes through a white cell.