题目描述

有一个 w \times h $n \times m$ 的网格，其中的 $2d$ 格包含整数 $1, 1, 2, 2, \ldots d, d$ ，保证这些格子都在网格的边界上。 (即第一行，第一列，第 $n$ 行或 第 $m$ 列)

你需要画出 $d$ 条路径以连接这 $d$ 对格子，每条路径由若干个竖直或水平的线段组成，路径不能走出网格，第 $i$ 条路径必须从数字 $i$ 所在的一个格子开始，并在另一个写着数字 $i$ 的格子结束，路径可以在某格的中心前进、左右转，但路径不能多次穿过同一个格子，两条不同的路径不能有公共点。格子允许不被经过。

给定这个网格，你需要构造一个合法的方案。如果不能，请输出 Impossible 。

输入格式

每个测试点包含多组数据。

对于每组数据，第一行包含三个整数 $n,m,d$ 。

接下来 $d$ 行，第 $i$ 行包含四个整数 $x_1,y_1,x_2,y_2$ ($1\leq x_1,x_2\leq n$, and $1\leq y_1,y_2\leq m$), 表示包含数字 $i$ 的两个格子的左边分别为 $(x_1,y_1), (x_2,y_2)$，这 $2d$ 个格子互不相同且保证在网格的边界上，左上角的格子坐标为 $(1,1)$, 右下角的是 $(n,m)$ 。

输出格式

对于每组数据，如果不可能画出这样的路径，输出一行 Impossible 。否则，在第一行输出 Possible ，并随后输出一个 $n$ 行 $m$ 列的包含你的方案的字符矩阵，格式如下。

对于在输入中有数字的格子，用 <, >, ^,v （分别代表左，右，上，下）来表示你设计的路径在这一格上的方向。

对于在输入中没有数字的路径经过的格子，使用 7, L, r, J, -, | （分别代表左下，右上，右下，左上，横向，纵向）来表示你设计的路径在这一格上的方向。

对于其它的格子，输出 . 既可。

数据不保证唯一解，你只需要输出一组可行解即可。

样例

6 5 3
5 1 1 3
6 3 2 5
6 2 6 1
3 3 4
1 1 2 1
1 2 3 3
1 3 2 3
3 1 3 2

Possible
.r<..
.L7.v
r-J.|
|...|
^...|
><>-J
Impossible

数据范围与提示

对于 $100\%$ 的数据， $1\leq n,m\leq 2000$, $d\ge 1$ 。

每个测试点中最多有 $50000$ 组测试数据，其中 $\sum nm$ 最多为 $4 \times 10^7$ 。

特别鸣谢楼天城和吉如一提供试题，数据。