Остання мураха#6779

Остання мураха

10 секунд

256 мегабайтів

Складна

Прямий тунель без відгалужень переповнений мурахами, які постійно приходять і йдуть. Деякі мурахи рухаються зліва направо, інші — справа наліво. Усі мурахи пересуваються з постійною швидкістю $1$ см/с. Коли дві мурахи зустрічаються, вони намагаються розминутися. Проте в деяких вузьких частинах тунелю це неможливо, і тоді мурахи розвертаються і рухаються в протилежних напрямках. Коли мураха досягає кінця тунелю, вона залишає його.

Довжина тунелю вимірюється в цілих сантиметрах. Вузькі ділянки розташовані на цілочисельних відстанях від обох кінців тунелю. Окрім цих ділянок, тунель достатньо широкий, щоб мурахи могли розминутися. Усі мурахи починають рух з різних вузьких ділянок. Нові мурахи не можуть проникнути в тунель, тому всі, хто в ньому є, зрештою його покинуть. Ваше завдання — написати програму, яка визначить, яка мураха залишить тунель останньою, і коли це станеться.

Малюнок 1 демонструє рух мурах протягом перших двох секунд у тунелі довжиною $6$ сантиметрів. Спочатку три мурахи, пронумеровані $1$ , $2$ і $3$ , починають рух з вузьких частин, розташованих на відстанях $1$ , $2$ і $5$ сантиметрів відповідно від лівого краю. Через $0.5$ секунд мурахи $1$ і $2$ зустрінуться в широкій частині і розминуться. Через дві секунди після початку руху мурахи $1$ і $3$ зустрінуться у вузькій частині і розвернуться.

Малюнок 1 відповідає першому тесту.

Малюнок 1. Рух мурах

Вхідні дані

Складається з кількох тестів. Кожен тест має наступний формат:

$n$ $l$

$d_{1}$ d_1 $p_{1}$ p_1

$d_{2}$ d_2 $p_{2}$ p_2

$...$

$d_{n}$ d_n $p_{n}$ p_n

Перший рядок тесту містить два цілі числа: $n$ ( $1 \leq n \leq 20$ 1 \le n \le 20) — кількість мурах, і $l$ ( $n + 1 \leq l \leq 100$ n + 1 \le l \le 100) — довжина тунелю в сантиметрах. Наступні $n$ рядків описують початковий стан мурах. Кожен рядок містить два числа: $d_{i}$ d_i і $p_{i}$ p_i. Мурахи пронумеровані від $1$ до $n$ . Мураха з номером $i$ має початковий напрямок $d_{i}$ d_i і початкове положення $p_{i}$ p_i. Напрямок $d_{i}$ d_i ( $1 \leq i \leq n$ 1 \le i \le n) може бути $L$ (вліво) або $R$ (вправо). Цілочисельне початкове положення $p_{i}$ p_i ( $1 \leq i \leq n$ 1 \le i \le n) вказує на відстань від лівого кінця тунелю в сантиметрах. Мурахи перераховані в порядку зліва направо, тобто $1 \leq p_{1} < p_{2} < ... < p_{n} \leq l - 1$ 1 \le p_1 < p_2 < ... < p_n \le l-1.

За останнім тестом слідує рядок з двох нулів.

Вихідні дані

Для кожного тесту виведіть кількість секунд, через які всі мурахи покинуть тунель, і номер мурахи, яка буде останньою. Якщо дві мурахи покинуть тунель одночасно, виведіть номер тієї, яка вийде з лівого боку.

Приклади

Приклад 1