Андрей муравей
Муравей Андрей очарован поведением своих друзей. Тысячами они прокладывают себе дорогу и снуют туда-сюда. Они способны строить высоко организованные муравейники. Но иногда они действуют немного глупо.
Недавно Андрей наблюдал за своими друзьями, марширующими по верху длинного куска дерева. Он заметил, что их модель поведения достаточно проста: каждый муравей двигается вперед с постоянной скоростью 1 сантиметр в секунду. Когда он встречает другого муравья, они только касаются друг друга своими антеннами и сразу же разворачиваются и продолжают движение в противоположном направлении. Если муравей достигнет конца палки, то он падает с нее и больше никогда не влияет на движение других муравьев.
Картинка вверху показывает пример движения муравьев в момент времени 0. Через одну секунду муравьи E и A встретятся в точке 2 и сменят свои направления движения. Потом муравей A встретится с B через следующие 1.5 секунды. В то же время (2.5 секунды после старта) встретятся муравьи C и D. Все четверо изменят направления. В следующие 0.5 секунды (время 3 секунды) первый муравей (E) упадет с левого края, и так далее.
Вам необходимо промоделировать движение муравьев. Для простоты считайте, что муравьи имеют нулевой размер (хотя на картинке изображено иначе).
Входные данные
Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей два целых числа - длина деревянной палки в сантиметрах l (1 ≤ l ≤ 99999) и количество муравьев в начале движения a (1 ≤ a ≤ l + 1).
Далее следуют a строк, каждая из которых содержит положительное целое число x[i], пробел и заглавная буква. Число x[i] (0 ≤ x[i] ≤ l) указывает на позицию i-го муравья, а буква на его начальное направление: "L" - влево (в направлении нуля) или "R" - вправо. Никакие два муравья не стартуют с одной и той же позиции.
Выходные данные
Для каждого теста вывести строку, содержащую текст "The last ant will fall down in t seconds - started at p.", где t - точное время, в которое последний муравей (или два) достигнет края дерева, а p - позиция, с которой стартовал этот муравей в момент времени 0. Если последними упадут два муравья одновременно, следует вывести "started at p and q", указывая их начальные позиции, p < q.