Задачи
Последний муравей
Последний муравей
Прямой тоннель без ответвлений переполнен занятыми муравьями, которые приходят и уходят. Некоторые муравьи движутся слева направо, а другие справа налево. Все муравьи движутся с постоянной скоростью \textbf{1} см/с. Когда два муравья встретятся, они пытаются разминуться друг с другом. Однако некоторые части тоннеля узкие и два муравья не могут там разминуться. Когда два муравья встречаются на узком участке, они разворачиваются и начинают двигаться в противоположных направлениях. Когда муравей достигает любого из концов тоннеля, он покидает его.
Длина тоннеля выражается целым числом сантиметров. Каждый узкий участок расположен на целочисленном расстоянии в сантиметрах от обоих концов тоннеля. Кроме этих участков, везде тоннель достаточно широк для того чтобы муравьи прошли друг мимо друга. Все муравьи начинают движение с разных узких участков. Ни один из новых муравьев не сможет проникнуть в тоннель. Следовательно все муравьи, находящиеся в тоннеле, в конце концов покинут его. Вам следует написать программу, которая сообщит, какой из муравьев последним покинет тоннель, а также когда это произойдет.
\textit{\textbf{Рисунок 1}} показывает передвижение муравьев в течение первых двух секунд в тоннеле длиной \textbf{6} сантиметров. Сначала три муравья, пронумерованных \textbf{1}, \textbf{2} и \textbf{3}, начинают движение из узких частей, расположенных на расстояниях \textbf{1}, \textbf{2} и \textbf{5} сантиметров соответственно от левого края. Через \textbf{0.5} секунд муравьи \textbf{1} и \textbf{2} встретятся в широкой части и разминутся друг с другом. Через две секунды после начала движения муравьи \textbf{1} и \textbf{3} встретятся в узкой части и развернутся.
\textit{\textbf{Рисунок 1}} соответствует первому тесту.
\includegraphics{https://static.e-olymp.com/content/7e/7e582bcec305f15aa9e331e0ffd6077b69b772f4.jpg}
\textit{\textbf{Рисунок 1}}. Движение муравьев
\InputFile
Состоит из нескольких тестов. Каждый тест имеет следующий формат:
\textbf{n l}
\textbf{d_1 p_1}
\textbf{d_2 p_2}
\textbf{...}
\textbf{d_n p_n}
Первая строка теста содержит два целых числа: \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{20}) - количество муравьев, и \textbf{l} (\textbf{n + 1} ≤ \textbf{l} ≤ \textbf{100}) - длина тоннеля в сантиметрах. Следующие \textbf{n} строк задают начальное состояние муравьев. Каждая строка содержит два числа: \textbf{d_i} и \textbf{p_i}. Муравьи пронумерованы числами от \textbf{1 }до \textbf{n}. Муравей с номером \textbf{i} имеет начальное направление \textbf{d_i} и начальное положение \textbf{p_i}. Направление \textbf{d_i} (\textbf{1} ≤ \textbf{i} ≤ \textbf{n}) принимает значение \textbf{L} (влево) или \textbf{R} (вправо). Целочисленное начальное положение \textbf{p_i} (\textbf{1} ≤ \textbf{i} ≤ \textbf{n}) указывает на расстояние от левого конца тоннеля в сантиметрах. Муравьи перечислены в порядке слева направо, то есть \textbf{1} ≤ \textbf{p_1} < \textbf{p_2} < ... < \textbf{p_n} ≤ \textbf{l−1}.
За последним тестом следует строка из двух нолей.
\OutputFile
Для каждого теста вывести количество секунд, через которое все муравьи покинут тоннель, и какой из муравьев будет последним. Необходимо указать номер последнего муравья. Если два муравья покинут тоннель одновременно, следует вывести номер того, который покинет тоннель с левой стороны.
Входные данные #1
3 6 R 1 L 2 L 5 1 10 R 1 2 10 R 5 L 7 2 10 R 3 L 8 2 99 R 1 L 98 4 10 L 1 R 2 L 8 R 9 6 10 R 2 R 3 L 4 R 6 L 7 L 8 0 0
Выходные данные #1
5 1 9 1 7 1 8 2 98 2 8 2 8 3