Юля не имеет никакого отношения к уральскому ACMу и попала в эту задачу только потому, что сама написала условие. Юля в университете предпочитала математику программированию, поэтому максимум может написать сортировку пузырьком на паскале, но зато она — серьёзный менеджер в крупной ИТ-компании. Как и у любого менеджера, у Юли бывают совещания. Не все совещания одинаково полезны, поэтому Юля очень ценит игры на телефоне, в которые можно сыграть за 1-2 минуты.

Так в Юлином телефоне поселились «Паровозики». Игра очень простая: на экране изображена карта железных дорог, все дороги оканчиваются разноцветными станциями или депо, на пересечениях дорог — стрелки. Из единственного депо один за другим выходят паровозики. Вовремя переводя стрелки, нужно направить каждый паровозик на станцию соответствующего цвета. Стоит на секунду отвлечься, и вот уже паровозики, как разноцветные тараканы, разбегаются в разные стороны, а ты не понимаешь, за что схватиться. В общем, нужно очень быстро и сосредоточенно тыкать в экран.

Как-то выглянув у Юли из-за плеча, паровозики увидел Дэнчик. Дэнчик, в отличие от Юли, опытный ACM-щик, поэтому он не хочет бездумно тыкать в экран, он хочет алгоритм. Сказано — сделано, через полчаса и три шота Б-52 в паровозики уже успешно играл написанный Дэнчиком бот.

Будь как Дэнчик! Реализуй алгоритм игры в паровозики. При этом помни, что если Юля как менеджер умеет планировать наперёд и переключает стрелки заранее, то Дэнчика мотивирует только приближающийся дедлайн, так что его бот переводит стрелку в тот момент, когда на ней оказывается паровозик.

В первой строке даны два числа N и M (2 ≤ N, M ≤ 500), далее идут 2 × N−1 строк по 2 × M−1 символов каждая — описание карты. На карте приняты следующие обозначения:

Гарантируется, что карта представляет из себя дерево, внутренними вершинами которого являются стрелки, листьями — депо или станции, причём депо ровно одно. Рёбрами дерева являются прямые участки пути (одно ребро — это один символ ’|’ или ’-’).

Положение стрелки задаёт направление, в котором через нее поедет поезд, стрелка не может направить поезд в точку вне железной дороги. Буква, указанная на карте на месте стрелки, показывает её начальное положение. Буква ’F’ означает, что поезд по дороге из депо, пересекая стрелку, поедет прямо, ’R’ — повернёт направо, ’L’ — повернёт налево.

В следующей строке дано одно число Q (1 ≤ Q ≤ 2 × 10⁵) — количество поездов, выезжающих из депо. Каждая из следующих Q строк содержит 3 числа T_i, X_i, Y_i (1 ≤ T_i ≤ 10⁹, 1 ≤ X_i ≤ N, 1 ≤ Y_i ≤ M) — время выхода i-го поезда из депо и координаты станции назначения. Поезда упорядочены в порядке возрастания времени выхода из депо.

В первой строке выведите единственное число R (0 ≤ R ≤ 2 × 10⁵) — минимальное количество необходимых переключений стрелок.

Каждая из следующих R строк должна содержать описание одного переключения — три числа T_i, X_i, Y_i и один символ C_i (C_i ∈ {’F’, ’L’, ’R’}), отделённый от Y_i ровно одним пробелом. Строка T_i X_i Y_i C_i указывает на то, что в момент времени T_i стрелку с координатой (X_i, Y_i) нужно переключить в сторону, соответствующую движению поезда: ’F’ — прямо, ’R’ — вправо, ’L’ — влево. Допускается переключение нескольких стрелок в один момент времени.

Гарантируется, что существует хотя бы одно решение с количеством переключений не более 2 × 10⁵. Если существует несколько решений — выведите любое из них.

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

В тот же момент времени 2 из депо покажется второй поезд. В момент времени 3 он будет находиться на стрелке, причём ему нужно ехать прямо. Так что стрелку придётся снова переключить. Получаем второе переключение: 3 1 2 F.

Третий поезд будет двигаться в том же направлении, что и второй, и стрелку переключать ему не нужно.