Digi Comp II#7854
Digi Comp II — це пристрій, у якому кульки потрапляють зверху і проходять шлях донизу через певний маршрут, визначений перемикачами. Кожного разу, коли кулька потрапляє на перемикач, вона рухається або вліво, або вправо, залежно від стану перемикача, і змінює цей стан. Абстрактно, цю машину можна змоделювати як орієнтований граф, де кожен перемикач представлений вершиною з вихідним ступенем , а кінцева вершина має вихідний ступінь . Одна з вершин перемикача є початковою і має вхідний ступінь . Кожна вершина-перемикач має внутрішній стан ( / ). Кулька починає свій шлях з початкової вершини і слідує маршрутом до кінцевої вершини, обираючи ліве або праве вихідне ребро на основі внутрішнього стану вершини-перемикача. Після проходження кульки внутрішній стан вершини змінюється. Кулька завжди рухається вниз, тому не може потрапити в цикл.
Цю машину можна "запрограмувати", задавши структуру графа, початкові стани кожної вершини-перемикача і кількість кульок, які в неї потрапляють. Результатом обчислень є стан перемикачів після завершення всіх проходжень. Цікаво, що можна реалізувати досить складні алгоритми, такі як додавання, множення, ділення і навіть стабільну проблему шлюбу. Проте ця задача не є обчислюваною за Тюрінгом.
Складаються з:
рядка, що містить два числа (0 \le n \le 10^{18}) і (1 \le m \le 500000) — кількість кульок і перемикачів у графі;
рядків, що описують перемикачі в порядку від до . Кожен рядок містить один символ ( або ) і два цілі числа і (0 \le L, R \le m), які описують початковий стан () перемикача і номери вершин, куди ведуть ліве () і праве () вихідне ребро. і можуть бути однаковими.
Вершина номер є кінцевою, а вершина номер — початковою. Граф не має циклів, тобто, проходячи через вершину, кулька вже до неї ніколи не повернеться.
Виведіть рядок з символів 'L' і 'R', що описує кінцевий стан перемикачів (в порядку від до ).
Приклад 1