Digi Comp II

The Digi Comp II is a machine where balls enter at the top and travel down through a circuit built from switches. When a ball lands on a switch it leaves to the left or to the right depending on the state of that switch, and the switch flips its state as the ball passes.

Model the machine as a directed graph. Every switch is a vertex of outdegree 2, and there is one extra end vertex of outdegree 0. One switch vertex is the start vertex and has indegree 0. The internal state of a switch vertex is either L or R. A ball starts at the start vertex and follows a path down to the end vertex. At a switch vertex it takes the left outgoing edge when the state is L and the right outgoing edge when the state is R, and the state of that vertex flips right after the ball passes through. A ball always moves down, so it never enters a loop.

You program the machine by choosing the graph structure, the initial state of every switch vertex, and the number of balls that enter. The result of the computation is the state of the switches once the last ball has left. Addition, multiplication, division and even the stable marriage problem can be programmed this way, but the machine is not Turing complete.

Given the graph, the initial states and the number of balls, report the final state of every switch.

The first line contains two integers $n$ and $m$, the number of balls and the number of switches ($0 \le n \le 10^{18}$, $1 \le m \le 500\,000$).

Each of the next $m$ lines describes switches 1 to $m$ in order. A line contains a character $c$ (L or R) and two integers $L$ and $R$ ($0 \le L, R \le m$). $c$ is the initial state of the switch, $L$ is the vertex the left outgoing edge points to, and $R$ is the vertex the right outgoing edge points to. $L$ and $R$ can be equal.

Vertex 0 is the end vertex and vertex 1 is the start vertex. The graph has no cycles, so a ball that has passed through a switch never returns to it.

Print one line with a string of length $m$ over the characters L and R, the final state of switches 1 to $m$ in order.