Problem B
Digi Comp II
One can “program” this machine by specifying the graph structure, the initial states of each switch vertex and the number of balls that enter. The result of the computation is the state of the switches at the end of the computation. Interestingly one can program quite sophisticated algorithms such as addition, multiplication, division and even the stable marriage problem. However, it is not Turing complete.
Input
The input consists of:

one line with two integers $n$ ($0\le n\le 10^{18}$) and $m$ ($1\le m\le 500\, 000$), the number of balls and the number of switches of the graph;

$m$ lines describing switches $1$ to $m$ in order. Each line consists of a single character $c$ (‘L’ or ‘R’) and two integers $L$ and $R$ ($0\le L,R\le m$), describing the initial state ($c$) of the switch and the destination vertex of the left ($L$) and right ($R$) outgoing edges. $L$ and $R$ can be equal.
Vertex number $0$ is the end vertex and vertex $1$ is the start vertex. There are no loops in the graph, i.e., after going through a switch a ball can never return to it.
Output
Output one line with a string of length $m$ consisting of the characters ‘L’ and ‘R’, describing the final state of the switches ($1$ to $m$ in order).
Sample Input 1  Sample Output 1 

5 3 L 2 3 R 0 3 L 0 0 
RLL 