Problem Description

Below is a Sudoku without numbers, only with relational symbols (yes, those pointed corners are "greater than" symbols)!

In addition to the relational constraints (note that adjacent cells cannot be the same), the usual Sudoku rules must also be satisfied:

• Each cell is a number from $1$ to $9$;
• Each row is a permutation of $1$ to $9$;
• Each column is a permutation of $1$ to $9$;
• Each $3 \times 3$ sub-matrix (separated by thick lines in the figure, there are a total of $3 \times 3$ such sub-matrices) is a permutation of $1$ to $9$.

As shown in the figure below, this is the only way to fill in the Sudoku mentioned above:

For aesthetic reasons, the relational constraints between all 12 pairs of adjacent cells in each $3 \times 3$ sub-matrix will be provided.

Input Format

There are a total of $15$ lines, containing an instance of the new Sudoku. The $1, 3, 5, 6, 8, 10, 11, 13, 15$ lines contain symbols for left-right direction (< and >), and the remaining lines contain symbols for up-down direction (^ and v).

Output Format

There are $9$ lines, each containing $9$ numbers from $1$ to $9$, separated by spaces. The input guarantees a unique solution.

Sample Input and Output

Input Sample #1

> < < < > <
v ^ v v ^ v ^ ^ v
< < < > < <
v ^ v ^ v v ^ ^ v
< < < < > >
< > > > < >
v v ^ ^ v ^ ^ v v
< > > < > >
^ v v v ^ v v ^ v
> < < > > >
< > > > > <
v v v v ^ ^ ^ ^ ^
> < < < < <
^ ^ ^ ^ ^ v v v ^
> > < > < <

Output Sample #1

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

Input Sample #2

< > > < > <
v v ^ ^ v v ^ ^ ^
< < > < > <
^ ^ ^ v ^ ^ ^ v v
< < < < > > 
> < > > > >
v ^ ^ ^ ^ v v v ^
> > > > < >
v v ^ v ^ v ^ v ^
> < < > > > 
< < < < > <
v ^ v v v v ^ ^ v
< > > < < >
^ v v v ^ v ^ v v
< > < > < >

Output Sample #2

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

见题面 Input 部分

见题面 Output 部分