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