Description

Below is a Sudoku with no digits, only inequality relations (yes, those chevrons are all "greater-than" signs):

Besides the inequality relations (note that adjacent cells cannot be equal), it must also satisfy the usual Sudoku rules:

• Each cell is a digit from $1 \sim 9$.
• Each row is a permutation of $1 \sim 9$.
• Each column is a permutation of $1 \sim 9$.
• Each $3 \times 3$ subgrid (separated by bold lines in the figure above; there are $3 \times 3$ such subgrids) is a permutation of $1 \sim 9$.

As shown below, there is exactly one way to fill the Sudoku above:

For neatness, for each $3 \times 3$ subgrid, the inequality relations for all $12$ pairs of adjacent cells will be given.

Input Format

There are $15$ lines in total, describing one instance of the new Sudoku. Lines $1, 3, 5, 6, 8, 10, 11, 13, 15$ contain left-right symbols (< and >), and the other lines contain up-down symbols (^ and v).

Output Format

Output $9$ lines, each containing $9$ digits from $1 \sim 9$, separated by spaces. The input guarantees a unique solution.

> < < < > <
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 ^
> > < > < <

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

< > > < > <
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
< > < > < >

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

Hint

Translated by ChatGPT 5