解题思路

把每个碎片看成图中的一个点，输入的每条关系$a\ b\ d$表示碎片$a$在碎片$b$的方向$d$上。

可以建立一个带方向的邻接关系：

• 若$d=U$，则$a$在$b$上方，坐标变化为$(-1,0)$
• 若$d=B$，则$a$在$b$下方，坐标变化为$(1,0)$
• 若$d=L$，则$a$在$b$左方，坐标变化为$(0,-1)$

题目内容

多多手里有一套散落的拼图，这套拼图可以完整的拼出 $n \times m$ 的矩形图片。拼图的每个碎片都有一个唯一的编号（从 $1$ 到 $n \times m$）。多多经过研究得到了一些碎片之间的相对位置关系，请帮他还原出最终的图片。

数据会给出一系列的相对关系，每条位置关系，描述为 $a$ $b$ $d$，代表编号 $a$、$b$ 的碎片相邻，并且 $a$ 碎片位于 $b$ 碎片的 $d$ 方向。$d$ 的取值范围为 $U、B、L、R$。其中：

• $U$ 代表 $a$ 在 $b$ 的上方
• $B$ 代表 $a$ 在 $b$ 的下方
• $L$ 代表 $a$ 在 $b$ 的左侧
• $R$ 代表 $a$ 在 $b$ 的右侧

特别说明：

1. 数据可能不包含所有的相邻关系，但数据保证根据这些相邻关系，一定能唯一地还原出最终的图片。数据不会出现相互矛盾的地方。

2. 不会出现拼成若干块，但没有相连，最后要靠边缘形状推理还原图片的情况。即数据保证连通性。

3. 图片方向是固定的，不需要考虑旋转的情况。

输入描述

第一行包含 $2$ 个正整数 $n, m$，分别表示拼图的行数、列数。

第二行包含 $1$ 个正整数 $k$，代表给出的相邻关系个数。

接下来 $k$ 行，每行包含两个正整数 $a, b$，以及字符 $d$，分别代表碎片编号和相对方位。$a, b, d$ 用一个空格隔开。

数据范围：

• $2 \le n, m \le 1000$
• $1 \le a, b < n \times m$
• $k \le 2 \times (n \times (m-1) + m \times (n-1))$

输出描述

样例1

输入

2 2
4
4 3 U
1 4 R
4 1 L
3 2 L

输出

4 1
3 2

样例2

输入

3 4
13
9 4 R
11 1 U
2 8 L
2 7 R
11 10 R
8 1 L
2 9 B
7 2 L
12 3 L
3 6 L
11 5 B
4 9 L
10 6 B

输出

12 3 6 5
4 9 10 11
7 2 8 1