Последний муравей
Прямой тоннель без ответвлений переполнен занятыми муравьями, которые приходят и уходят. Некоторые муравьи движутся слева направо, а другие справа налево. Все муравьи движутся с постоянной скоростью 1 см/с. Когда два муравья встретятся, они пытаются разминуться друг с другом. Однако некоторые части тоннеля узкие и два муравья не могут там разминуться. Когда два муравья встречаются на узком участке, они разворачиваются и начинают двигаться в противоположных направлениях. Когда муравей достигает любого из концов тоннеля, он покидает его.
Длина тоннеля выражается целым числом сантиметров. Каждый узкий участок расположен на целочисленном расстоянии в сантиметрах от обоих концов тоннеля. Кроме этих участков, везде тоннель достаточно широк для того чтобы муравьи прошли друг мимо друга. Все муравьи начинают движение с разных узких участков. Ни один из новых муравьев не сможет проникнуть в тоннель. Следовательно все муравьи, находящиеся в тоннеле, в конце концов покинут его. Вам следует написать программу, которая сообщит, какой из муравьев последним покинет тоннель, а также когда это произойдет.
Рисунок 1 показывает передвижение муравьев в течение первых двух секунд в тоннеле длиной 6 сантиметров. Сначала три муравья, пронумерованных 1, 2 и 3, начинают движение из узких частей, расположенных на расстояниях 1, 2 и 5 сантиметров соответственно от левого края. Через 0.5 секунд муравьи 1 и 2 встретятся в широкой части и разминутся друг с другом. Через две секунды после начала движения муравьи 1 и 3 встретятся в узкой части и развернутся.
Рисунок 1 соответствует первому тесту.
Рисунок 1. Движение муравьев
Входные данные
Состоит из нескольких тестов. Каждый тест имеет следующий формат:
n l
d_1 p_1
d_2 p_2
...
d_n p_n
Первая строка теста содержит два целых числа: n (1 ≤ n ≤ 20) - количество муравьев, и l (n + 1 ≤ l ≤ 100) - длина тоннеля в сантиметрах. Следующие n строк задают начальное состояние муравьев. Каждая строка содержит два числа: d_i и p_i. Муравьи пронумерованы числами от 1 до n. Муравей с номером i имеет начальное направление d_i и начальное положение p_i. Направление d_i (1 ≤ i ≤ n) принимает значение L (влево) или R (вправо). Целочисленное начальное положение p_i (1 ≤ i ≤ n) указывает на расстояние от левого конца тоннеля в сантиметрах. Муравьи перечислены в порядке слева направо, то есть 1 ≤ p_1 < p_2 < ... < p_n ≤ l−1.
За последним тестом следует строка из двух нолей.
Выходные данные
Для каждого теста вывести количество секунд, через которое все муравьи покинут тоннель, и какой из муравьев будет последним. Необходимо указать номер последнего муравья. Если два муравья покинут тоннель одновременно, следует вывести номер того, который покинет тоннель с левой стороны.