아래로 파헤치기

디나와 디마는 다뉴브 삼각주(현대 도브루자 지역)에서 다키아 문화(아마도 데케발루스 왕 본인)의 것으로 추정되는 고대 모자이크 계단을 탐사하는 젊은 고고학자이다.

각 계단 단은 8개의 모자이크 조각으로 덮여 있고, 각 조각은 흰색 또는 빨간색이다. 매일 아침 두 사람은 계단에서 정확히 한 단을 파낸다. 물론 위에서 아래로 파낸다.

점심을 먹고 작업 구역으로 향하며 계단을 내려가는 매일 오후, 두 사람은 게임을 한다. 가장 위쪽 단에 손수건을 (아주 조심스럽게) 올려놓는다. 그다음 디나부터 번갈아 가며 수를 둔다. 각 수에서 플레이어는 손수건을 몇 단 아래로 내린다. 두 단 사이의 거리가 두 단의 공통 모자이크 조각 수(같은 위치에 같은 색으로 놓인 쌍의 수)보다 작거나 같을 때에만 손수건을 한 단에서 더 낮은 단으로 내릴 수 있다. 수를 둘 수 없는 플레이어가 오늘 게임에서 진다.

예를 들어, 여기서 디나는 손수건을 가장 위쪽 단에서 가운데 단으로 내릴 수 있고($1 \le 7$이므로), 아래쪽 단으로도 내릴 수 있다($2 \le 6$이므로).

각 오후마다 두 사람이 최적으로 플레이할 때 누가 게임에서 이기는지 구하시오.

첫째 줄에 정수 $n$이 주어진다($1 \le n \le 300\,000$). 이는 계단의 높이이다.

다음 $n$개 줄에는 각각 8개의 문자 'W' 또는 'R'이 주어진다. 이는 위에서 아래로 각 단을 나타낸다.

$n$개의 숫자를 한 줄에 출력한다. 각 숫자는 각 오후 게임에 대응한다. 1은 디나가 이김을, 2는 디마가 이김을 의미한다.