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).