| Codeforces Round 165 (Div. 1) |
|---|
| Закончено |
Эмускальд — музыкант-новатор, он всегда пытается выйти за рамки творения музыки. Теперь он придумал революционный музыкальный инструмент — прямоугольную арфу.
Прямоугольная арфа является прямоугольником n × m единиц, она состоит из n рядов и m столбцов. Ряды пронумерованы от 1 до n сверху вниз. Аналогично, столбцы пронумерованы от 1 до m слева направо. Крепления для струн расположены равномерно по каждой стороне, по одному креплению на единице длины. Таким образом, существует по n креплений на левой и правой сторонах арфы и по m креплений на верхней и нижней сторонах. Арфа имеет ровно n + m различных струн, каждая струна соединяет два разных крепления, расположенных на разных сторонах арфы.
Эмускальд приказал своему ученику изготовить первую в мире прямоугольную арфу. Однако, он не упомянул, что никакие две струны не могут пересекаться (если струны пересекаются, то играть на арфе невозможно). Две струны пересекаются, если отрезки, соединяющие их крепления, пересекаются. Чтобы исправить арфу, Эмускальд может выполнять операции двух типов:
- выбрать два различных столбца и поменять их крепления на каждой стороне арфы, не меняя сцепления каждой струны;
- выбрать два различных ряда и поменять их крепления на каждой стороне арфы, не меняя сцепления каждой струны.
В следующем примере он может починить арфу, поменяв местами два столбца:
Помогите Эмускальду завершить свое детище и найдите перестановки, показывающие, как надо расположить ряды и колонки арфы. В противном случае сообщите, что сделать это невозможно. Юноша может снимать и натягивать струны на крепления, так что физическое расположение струн не имеет значения.
Первая строка входных данных содержит два целых числа n и m (1 ≤ n, m ≤ 105), разделенных пробелами, высота и ширина арфы в единицах. Каждая из следующих n + m строк содержит четыре токена через пробел, описывающих одну струну: два символа ai, bi, и два целых числа pi, qi. Пара ai и pi описывает первое крепление, а пара bi и qi описывает второе крепление струны.
Пара s, x описывает положение одного крепления следующим образом:
- s равняется одному из символов «L», «T», «R» или «B» (без кавычек), и означает, что крепление находится на левой, верхней, правой или нижней границе арфы соответственно;
- x равняется номеру ряда, если крепление находится на левой или правой границе арфы, и номеру столбца, если крепление находится на верхней или нижней границе арфы.
Гарантируется, что никакие две струны не присоединены к одному и тому же креплению.
Если можно переставить ряды и столбцы так, чтобы исправить арфу, в первой строке выведите n целых чисел — старые номера рядов, теперь размещенные сверху вниз в исправленной арфе. Во второй строке выведите m целых чисел, разделенных пробелом — старые номера столбцов, теперь расположенные слева направо в исправленной арфе.
Если же невозможно переставить ряды и столбцы так, чтобы исправить арфу, выведите «No solution» (без кавычек).
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 2 3
3 2 1 4
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
No solution
