Emuskald 是一位富有创新精神的音乐家,始终致力于突破音乐制作的界限。现在他想出了一种革命性乐器的想法——矩形竖琴。
矩形竖琴是由 n 行和 m 列组成的 n × m 矩形。行从上到下编号为 1 到 n。同样,列从左到右编号为 1 到 m。琴弦销钉均匀分布在每一侧,每个单元一个。因此,竖琴的左右两侧有 n 个销钉,顶部和底部有 m 个销钉。竖琴有 n + m 根不同的弦,每根弦连接两个不同的引脚,每个引脚位于竖琴的不同一侧。
埃穆斯卡德命令他的学徒建造第一把矩形竖琴。不过,他并没有提到两根弦不能交叉,否则就无法弹奏竖琴。如果连接销钉的线段相交,两根弦就会交叉。为了修复竖琴,Emuskald 可以执行两种类型的操作:
1. 选择两个不同的列并交换竖琴两侧的引脚,而不更改连接每根弦的引脚;
2. 选择两个不同的行并交换竖琴两侧的引脚,而不更改连接每根弦的引脚;
在下面的示例中,他可以通过交换两列来修复竖琴:
帮助 Emuskald 完成他的创作并找到竖琴的行和列需要重新排列的排列,或者告诉它不可能这样做。他可以将每根琴弦拆开并重新连接到其销钉上,因此琴弦的物理布局并不重要。
输入
输入的第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 105),以单位表示竖琴的高度和宽度。以下 n + m 行中的每一行都包含 4 个以空格分隔的标记,描述单个字符串:两个符号 ai、bi 和两个整数 pi、qi。 ai、pi 对描述第一个引脚,bi、qi 对描述字符串的第二个引脚;
一对 s, x 按以下方式描述单个引脚的位置:
1. s 等于符号“L”、“T”、“R”或“B”之一(不带引号),这意味着引脚相应地位于竖琴的左侧、顶部、右侧或底部;
2. 如果引脚位于竖琴的左边界或右边界,则 x 等于行号;如果引脚位于竖琴的上边界或下边界,则 x 等于列号。
确保没有两个不同的字符串连接到同一引脚。
输出
如果可以重新排列行和列来固定竖琴,请在第一行输出 n 个空格分隔的整数 - 现在在固定竖琴中从上到下放置的旧行数。在第二行,输出 m 个空格分隔的整数 - 现在固定竖琴中从左到右放置的旧列数。
如果无法重新排列行和列来修复竖琴,则输出“无解决方案”(不带引号)。
示例
输入 #1
3 4 L T 1 3 L B 2 2 L B 3 3 T R 1 2 T B 2 1 T R 4 1 B R 4 3
输出 #1
1 2 3 3 2 1 4
输入 #2
3 3 L T 1 1 T R 3 1 R B 3 3 B L 1 3 L R 2 2 T B 2 2
输出 #2
No solution