[CQOI2013] 新数独

题目描述

下面是一个没有数字,只有大小关系(没错,那些尖角都是“大于符号”)!的数独: ![](https://cdn.luogu.com.cn/upload/image_hosting/wm5lvhj6.png) 除了大小关系外(注意相邻格子不能相同),还需要满足通常的数独规则: * 每个格子都是 $1\sim 9$ 的数字; * 每行都是 $1 \sim 9$ 的排列; * 每列都是 $1 \sim 9$ 的排列; * 每个 $3\times 3$ 的子矩阵(上图中用粗线隔开,一共有 $3\times 3$ 个这样的子矩阵)都是 $1\sim 9$ 的排列。 如下图所示,是上述提到的数独的唯一一种填法: ![](https://cdn.luogu.com.cn/upload/image_hosting/73a6a29i.png) 为了美观,每个 $3\times 3$ 子矩阵的**所有 $12$ 对**相邻格子的大小关系都将给出。

输入输出格式

输入格式


一共 $15$ 行,包含一个新数独的实例。第 $1,3,5,6,8,10,11,13,15$ 行包含左右方向的符号(< 和 >),其余行包含上下方向的符号(^ 和 v)

输出格式


包含 $9$ 行,每行 $9$ 个 $1\sim 9$ 的数字,以空格隔开。输入保证唯一解。

输入输出样例

输入样例 #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 ^
> > < > < <

输出样例 #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

输入样例 #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
< > < > < >

输出样例 #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