Problem Description

Among the employees of Recruit Holdings, a number puzzle is becoming popular.

The number puzzle that the employees are playing involves filling a grid of 9 rows and 9 columns with digits from 1 to 9. However, the digits written must satisfy the following conditions:

• In each row, the same digit does not appear more than once.
• In each column, the same digit does not appear more than once.
• For any square, the digit in that square does not appear in any of the squares that a knight's piece in chess can move to in one move (see the figure).

Figure. If you place a knight's piece on the black square, it can move to any of the 8 white circles in one move.

You have been tasked with writing a program to check the solutions. Given a 9x9 grid with digits from 1 to 9 written in each square, create a program to check if it satisfies the above conditions.

Input Format

The input is given in the following format, where the digit in the i-th row and j-th column is \( s_{ij} \):

\( s_{11}s_{12} \) ... \( s_{19} \) : \( s_{91}s_{92} \) ... \( s_{99} \)

Output Format

Output Yes if the conditions are satisfied, otherwise output No.

Sample Input and Output

Sample Input #1

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

Sample Output #1

Yes

Sample Input #2

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345679

Sample Output #2

No

Sample Input #3

123456789
234567891
345678912
456789123
567891234
678912345
789123456
912345678
891234567

Sample Output #3

No

Notes/Hints

Constraints

• \( s_{ij} \) \( (1 \leq i, j \leq 9) \) is a digit from 1 to 9

Sample Explanation 1

All three conditions are satisfied.

Sample Explanation 2

The last row contains two 9s, so it does not satisfy the first condition. Similarly, it does not satisfy the second condition.

Sample Explanation 3

The square in the 7th row and 3rd column and the square in the 8th row and 1st column can be reached by a knight's move. However, these two squares contain the same digit, so the third condition is not satisfied.

见题面 Input 部分

见题面 Output 部分