Андрій мураха
Мураха Андрій зачарований поведінкою своїх друзів. Тисячами вони прокладають собі дорогу і снують туди-сюди. Вони здатні будувати високо організовані мурашники. Але іноді вони діють трохи нерозумно.
Нещодавно Андрій спостерігав за своїми друзями, які марширують по верху довгого шматка дерева. Він помітив, що їхня модель поведінки досить проста: кожна мураха рухається вперед з постійною швидкістю 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.