题目描述

有一个 $n \times m$ 的网格，其中的 $2d$ 个格子包含整数 $1,1,2,2,\dots,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$，且 $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$。