P4573 [CQOI2013] New Sudoku

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.

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 $9$ lines, each containing $9$ digits from $1 \sim 9$, separated by spaces. The input guarantees a unique solution.

Translated by ChatGPT 5