Epic Win!

가위바위보에서는 두 사람이 매 라운드마다 동시에 바위, 보, 가위 중 하나를 낸다. 같은 것을 내면 무승부이고, 그렇지 않으면 바위는 가위를 이기고 보는 바위를 이기고 가위는 보를 이긴다.

이 문제에서는 두 유한 상태 기계가 이 게임을 끝없이 반복한다. 형식적으로 여기서 기계는 무어 기계를 뜻한다.

가위바위보를 하는 기계의 상태는 유한개다. 각 상태는 두 가지를 정한다. 다음 라운드에 낼 수, 그리고 상대가 바위, 보, 가위를 냈을 때 각각 옮겨 갈 다음 상태다. 두 기계 모두 라운드가 끝난 뒤에야 상대가 낸 수를 안다.

당신은 상대 기계의 설계를 전부 알고 있다. 딱 하나, 상대가 어느 상태에서 시작하는지는 모른다. 그래도 당신의 기계는 처음 $10^9$ 라운드 중 99% 이상을 이겨야 한다. 이것을 epic win이라고 부른다.

조건을 만족하는 기계는 여러 가지다. 이 문제는 그중 하나를 정확히 지정한다. 아래 절차대로 기계를 만들어 출력한다.

상대 상태에 1부터 $n$까지 번호를 붙인다. 상태 $q$에서 내는 수를 $move(q)$로 쓰고, 당신이 $x$를 냈을 때 상태 $q$에서 옮겨 가는 상대의 다음 상태를 $next(q, x)$로 쓴다.

분리 거리. 상대 상태의 순서쌍 $(a, b)$에 대해 $e(a, b)$를 다음과 같이 정의한다. $move(a) \ne move(b)$이면 $e(a, b) = 1$이다. 그렇지 않으면 세 가지 수 $x$에 대해 $e(a, b) = 1 + \min_x e(next(a, x), next(b, x))$이다. 당신이 수를 어떻게 골라도 두 상태가 서로 다른 수를 내는 라운드가 오지 않으면 $e(a, b) = \infty$로 둔다. $a = b$인 쌍은 항상 $\infty$다.

후보 집합. 후보 집합은 상대 상태의 공집합이 아닌 부분집합이다. 후보 집합 $B$를 다음 규칙으로 줄인다. 서로 다른 모든 $a, b \in B$에 대해 $e(a, b) = \infty$이면 $B$를 $B$의 가장 작은 원소 하나만 남긴 집합으로 바꾸고, 그렇지 않으면 $B$를 그대로 둔다. 이렇게 줄인 후보 집합 하나가 당신 기계의 상태 하나가 된다.

줄인 집합 $B$에서 내는 수는 다음과 같다.

1. $B$의 원소가 하나뿐이면, 즉 $B = \{q\}$이면 $move(q)$를 이기는 수를 낸다.
2. 그렇지 않으면 $a < b$이고 $a, b \in B$이고 $e(a, b)$가 유한한 쌍 $(a, b)$ 중에서 $e(a, b)$를 먼저, 그다음 $a$, 그다음 $b$를 비교해 가장 작은 쌍을 고른다. 그리고 바위, 보, 가위 순서로 살펴보면서 $e(next(a, x), next(b, x))$를 최소로 만드는 첫 번째 수 $x$를 낸다. 여기서 $\infty$는 어떤 정수보다도 크다고 본다.

$B$의 전이는 다음과 같다. 위에서 고른 수를 $x$라 하고, 관측한 상대의 수를 $m$이라 한다. $B_m = \{q \in B : move(q) = m\}$이라 하면, $B_m$이 공집합일 때 $m$에 대한 전이는 1번 상태로 간다. 공집합이 아니면 $\{next(q, x) : q \in B_m\}$을 줄인 집합으로 간다.

번호는 다음 순서로 붙인다. 1번 상태는 전체 집합 $\{1, 2, \dots, n\}$을 줄인 집합이다. 번호가 작은 상태부터 차례로 처리하고, 한 상태에서는 관측한 수를 바위, 보, 가위 순으로 살펴본다. 아직 번호가 없는 집합이 나올 때마다 비어 있는 가장 작은 번호를 준다. 같은 집합에는 항상 같은 번호가 붙는다. 출력도 이 번호 순서로 한다.

첫 줄에 상대 기계의 상태 개수 $n$이 주어진다 ($1 \le n \le 100$). 상태 번호는 1부터 $n$까지다.

다음 $n$개 줄에는 상태 하나의 정보가 주어진다. $i$번째 줄은 문자 $c_i$와 정수 $r_i$, $p_i$, $s_i$로 이루어진다. $c_i$는 R, P, S 중 하나이고 $i$번 상태에서 내는 수를 뜻한다. $r_i$, $p_i$, $s_i$는 당신이 각각 바위, 보, 가위를 냈을 때 $i$번 상태에서 옮겨 가는 다음 상태다 ($1 \le r_i, p_i, s_i \le n$).

첫 줄에 당신 기계의 상태 개수 $k$를 출력한다.

이어서 $k$개 줄에 입력과 같은 형식으로 각 상태를 출력한다. 그 상태에서 내는 수를 R, P, S 중 하나로 쓰고, 관측한 상대의 수가 바위, 보, 가위일 때 각각 옮겨 가는 다음 상태를 쓴다.

1번 상태가 당신 기계의 시작 상태다. 이 문제의 모든 입력에서 위 절차로 만든 기계의 상태 개수는 50000을 넘지 않는다.

$t$번째 라운드까지 관측한 결과와 앞뒤가 맞는 상대 상태를 모두 모으면 그것이 당신 기계의 현재 후보 집합이다. 서로 구별할 수 없는 상태를 하나로 줄인 부분만 다르다. 그래서 후보 집합의 원소가 하나로 줄면 상대가 앞으로 낼 수를 전부 알고, 남은 모든 라운드를 이긴다.

매 라운드마다 후보 집합이 작아지거나 고른 쌍의 분리 거리가 1 줄어든다. 분리 거리는 $n - 1$을 넘지 않고 집합은 $n - 1$번보다 많이 작아질 수 없으므로, 이기지 못하는 라운드는 $n^2$번보다 적다. $10^9$의 1%에 한참 못 미치는 수다.