1976. Лифты

Чтобы получить разрешение на строительство Омнигенерического Ультимата в полом нутре Рапундры, огромной луны недотяпов, конструктор Клапауций отправился в столицу их планеты, где обнаружил, что все министерства планеты размещались в новом многоэтажном здании, и теперь для получения необходимых подписей и печатей посетителям не требовалось ездить в разные концы города.

Здание было снабжено сложной системой лифтов. Лифты не управлялись пассажирами, а двигались автоматически. Например, один из лифтов останавливался для высадки и посадки пассажиров через каждые 5 этажей, а другой – через каждые 12 этажей. При этом время поездки на любом из лифтов не зависело от количества этажей и равнялось 1 пякунде (единица измерения времени недотяпов, около 5 секунд). Например, пусть лифт в 10-этажном здании, который проезжает за поездку 3 этажа, находится на пятом этаже и движется вниз. Тогда через пякунду он будет на втором этаже, затем опять на пятом, потом на восьмом, затем спустится на пятый и так далее. Движение лифтов было синхронизировано таким образом, что в конце каждой пякунды все лифты останавливались, и можно было выйти и перейти в другой лифт, если он в этот момент был на том же этаже. Кроме того, в здании имелась лестница, по которой можно было за одну пякунду подняться или спуститься на один этаж. Можно также стоять на этаже и ждать лифта.

Напишите программу, которая поможет Клапауцию быстро путешествовать по зданию.

Во входном файле в первой строке содержатся четыре целых числа, разделенных пробелами – количество этажей в здании `H` (`1\ <\ H\ ≤\ 1000`), количество лифтов `N` (`1\ ≤\ N\ ≤\ 100`), номер этажа `A` (`1\ ≤\ A\ ≤\ H`), на котором находится Клапауций, и номер этажа `B` (`1\ ≤\ B\ ≤\ H`), на который требуется попасть Клапауцию. Далее следует `N` строк, содержащих по три целых числа, разделенных пробелами – номер этажа `P_i` (`1\ ≤\ P_i\ ≤\ H`), на котором находится лифт в начальный момент путешествия Клапауция, число этажей `S_i` (`1\ ≤\ S_i\ ≤\ H/2`), на которое лифт поднимается или спускается за одну пякундную поездку, и направление движения лифта в следующий интервал времени `D_i` (`D_i\ =\ 1`, если лифт поедет вверх, `D_i\ =\ –1`, если лифт поедет вниз).

В выходной файл вывести одну строку, содержащую два целых числа, разделенных пробелом – время в пякундах, необходимое Клапауцию, чтобы добраться до нужного этажа, и количество этажей, которое Клапауцию придется пройти по лестнице. Требуется минимизировать в первую очередь время путешествия, а затем количество этажей, на которое Клапауцию придется подняться или спуститься без помощи лифта.

10 2 1 9
5 3 –1
1 1 1

4 1