ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2016

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

J. Паровозики

Ограничение времени: 4.0 секунды
Ограничение памяти: 256 МБ
Юля не имеет никакого отношения к уральскому ACMу и попала в эту задачу только потому, что сама написала условие. Юля в университете предпочитала математику программированию, поэтому максимум может написать сортировку пузырьком на паскале, но зато она — серьёзный менеджер в крупной ИТ-компании. Как и у любого менеджера, у Юли бывают совещания. Не все совещания одинаково полезны, поэтому Юля очень ценит игры на телефоне, в которые можно сыграть за 1-2 минуты.
Так в Юлином телефоне поселились «Паровозики». Игра очень простая: на экране изображена карта железных дорог, все дороги оканчиваются разноцветными станциями или депо, на пересечениях дорог — стрелки. Из единственного депо один за другим выходят паровозики. Вовремя переводя стрелки, нужно направить каждый паровозик на станцию соответствующего цвета. Стоит на секунду отвлечься, и вот уже паровозики, как разноцветные тараканы, разбегаются в разные стороны, а ты не понимаешь, за что схватиться. В общем, нужно очень быстро и сосредоточенно тыкать в экран.
Как-то выглянув у Юли из-за плеча, паровозики увидел Дэнчик. Дэнчик, в отличие от Юли, опытный ACM-щик, поэтому он не хочет бездумно тыкать в экран, он хочет алгоритм. Сказано — сделано, через полчаса и три шота Б-52 в паровозики уже успешно играл написанный Дэнчиком бот.
Будь как Дэнчик! Реализуй алгоритм игры в паровозики. При этом помни, что если Юля как менеджер умеет планировать наперёд и переключает стрелки заранее, то Дэнчика мотивирует только приближающийся дедлайн, так что его бот переводит стрелку в тот момент, когда на ней оказывается паровозик.

Исходные данные

В первой строке даны два числа N и M (2 ≤ N, M ≤ 500), далее идут 2 × N−1 строк по 2 × M−1 символов каждая — описание карты. На карте приняты следующие обозначения:
  • ’S’ — депо;
  • ’X’ — станция;
  • ’F’, ’L’, ’R’ — стрелка;
  • ’|’ (вертикальная черта, десятичный ASCII-код 124), ’-’ (дефис, десятичный ASCII-код 45) — прямые участки пути;
  • ’.’ (точка, десятичный ASCII-код 46) — точка вне железной дороги.
Гарантируется, что карта представляет из себя дерево, внутренними вершинами которого являются стрелки, листьями — депо или станции, причём депо ровно одно. Рёбрами дерева являются прямые участки пути (одно ребро — это один символ ’|’ или ’-’).
Положение стрелки задаёт направление, в котором через нее поедет поезд, стрелка не может направить поезд в точку вне железной дороги. Буква, указанная на карте на месте стрелки, показывает её начальное положение. Буква ’F’ означает, что поезд по дороге из депо, пересекая стрелку, поедет прямо, ’R’ — повернёт направо, ’L’ — повернёт налево.
В следующей строке дано одно число Q (1 ≤ Q ≤ 2 × 105) — количество поездов, выезжающих из депо. Каждая из следующих Q строк содержит 3 числа Ti, Xi, Yi (1 ≤ Ti ≤ 109, 1 ≤ XiN, 1 ≤ YiM) — время выхода i-го поезда из депо и координаты станции назначения. Поезда упорядочены в порядке возрастания времени выхода из депо.

Результат

В первой строке выведите единственное число R (0 ≤ R ≤ 2 × 105) — минимальное количество необходимых переключений стрелок.
Каждая из следующих R строк должна содержать описание одного переключения — три числа Ti, Xi, Yi и один символ Ci (Ci ∈ {’F’, ’L’, ’R’}), отделённый от Yi ровно одним пробелом. Строка Ti Xi Yi Ci указывает на то, что в момент времени Ti стрелку с координатой (Xi, Yi) нужно переключить в сторону, соответствующую движению поезда: ’F’ — прямо, ’R’ — вправо, ’L’ — влево. Допускается переключение нескольких стрелок в один момент времени.
Гарантируется, что существует хотя бы одно решение с количеством переключений не более 2 × 105. Если существует несколько решений — выведите любое из них.

Примеры

исходные данныерезультат
3 3
S-F-X
..|..
L-R-R
|...|
X.X-R
4
1 1 3
2 3 1
4 1 3
6 3 2
4
3 1 2 R
5 1 2 F
7 1 2 R
8 2 2 L
2 3
S-F-X
..|..
..X..
3
1 2 2
2 1 3
4 1 3
2
2 1 2 R
3 1 2 F

Замечания

Рассмотрим второй пример подробнее. На карте расположено депо, две станции, три участка пути и стрелка. Положение стрелки в начальный момент времени таково, что поезд через нее поедет прямо. Всего у стрелки два возможных положения — прямо и направо. В момент времени 1 из депо покажется поезд. За единицу времени поезд пройдёт единицу пути и в момент времени 2 окажется на стрелке. Чтобы попасть в пункт назначения, поезду нужно на стрелке повернуть направо, так что стрелку нужно переключить в положение «направо». Получаем первое переключение: 2 1 2 R.
В тот же момент времени 2 из депо покажется второй поезд. В момент времени 3 он будет находиться на стрелке, причём ему нужно ехать прямо. Так что стрелку придётся снова переключить. Получаем второе переключение: 3 1 2 F.
Третий поезд будет двигаться в том же направлении, что и второй, и стрелку переключать ему не нужно.
Автор задачи: Денис Мухаметьянов
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2087. Паровозики