Digi Comp II

Digi Comp II는 위에서 공을 넣으면 스위치로 짜인 회로를 따라 공이 아래로 내려가는 기계다. 공이 스위치에 떨어지면 그 스위치의 상태에 따라 왼쪽이나 오른쪽으로 빠져나가고, 공이 지나가는 순간 스위치의 상태가 반대로 바뀐다.

이 기계는 방향 그래프로 나타낸다. 스위치 하나마다 나가는 간선이 2개인 정점이 하나씩 있고, 나가는 간선이 없는 끝 정점이 하나 더 있다. 스위치 정점 중 하나는 시작 정점이며 들어오는 간선이 없다. 각 스위치 정점의 내부 상태는 L 아니면 R이다. 공은 시작 정점에서 출발해 끝 정점까지 내려가고, 스위치 정점에서는 상태가 L이면 왼쪽 간선을, R이면 오른쪽 간선을 고른다. 공이 지나간 직후 그 정점의 상태는 반대로 바뀐다. 공은 늘 아래로만 움직이므로 같은 스위치를 다시 만나지 않는다.

그래프 구조, 각 스위치의 초기 상태, 넣을 공의 개수를 정하는 것이 이 기계를 프로그래밍하는 방법이다. 계산 결과는 마지막 공이 빠져나간 뒤의 스위치 상태다. 덧셈, 곱셈, 나눗셈은 물론 안정 결혼 문제까지 이런 식으로 프로그래밍할 수 있지만, 이 기계는 튜링 완전하지 않다.

그래프와 초기 상태, 공의 개수가 주어질 때 모든 스위치의 최종 상태를 구하는 문제다.

첫째 줄에 공의 개수 $n$과 스위치의 개수 $m$이 주어진다. ($0 \le n \le 10^{18}$, $1 \le m \le 500\,000$)

다음 $m$개 줄에는 1번 스위치부터 $m$번 스위치까지의 정보가 차례대로 주어진다. 각 줄은 문자 $c$ (L 또는 R)와 두 정수 $L$, $R$로 이루어진다. ($0 \le L, R \le m$) $c$는 스위치의 초기 상태이고, $L$은 왼쪽 간선이 향하는 정점 번호, $R$은 오른쪽 간선이 향하는 정점 번호다. $L$과 $R$은 같을 수 있다.

0번 정점은 끝 정점이고 1번 정점은 시작 정점이다. 그래프에 사이클은 없다. 즉 어떤 스위치를 지난 공이 그 스위치로 되돌아오는 일은 없다.

1번 스위치부터 $m$번 스위치까지의 최종 상태를 순서대로 이어 붙인, L과 R로 이루어진 길이 $m$의 문자열을 한 줄에 출력한다.