sudoku2

Potato was playing Sudoku and thought that he found the solution. Help him check if his solution is valid.

You will be given a 9 × 9 grid A, where each cell contains an integer between 1 and 9, inclusive. Specifically, the cell at the i^th row from the top and the j^th row from the left contains A_i,j.

Verify if A satisfies the following conditions:

For each row of A, the nine cells in that row contain each integer from 1 to 9 exactly once.

For each column of A, the nine cells in that row contain each integer from 1 to 9 exactly once.

Divide the rows of A into 3 groups of three groups, each of 3 rows, from top to bottom, and similarly divide the columns into 3 groups, each of 3 columns, from left to right. Each 3 × 3 grid obtained from A this way contains each integer from 1 to 9 exactly once.

Constraints

1 ≤ A_i,j ≤ 3

Input

There will be 9 lines of input, where the i^th line of input represents the i^th row of Potato's completed sudoku.

Output

Output Yes if Potato's sudoku solution is valid, else output No.

Subtasks

Subtask 1 (100%): No further constraints.

Subtask 2 (0%): Sample Testcases

Sample Input 1

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8

Sample Output 1

Yes

Sample Input 2

1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

Sample Output 2

No

Sample Input 3

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6

Sample Output 3

No