Epic Win!

In rock-paper-scissors two players show a move at the same time in every round: Rock, Paper, or Scissors. Equal moves are a draw. Otherwise Rock beats Scissors, Paper beats Rock, and Scissors beats Paper.

In this problem two finite state machines repeat this game forever. Formally, machine here means a Moore machine.

A machine that plays rock-paper-scissors has finitely many states. Each state fixes two things: the move shown in the coming round, and the state the machine moves to when its opponent shows Rock, Paper, or Scissors. Both machines learn the opponent's move only after the round is over.

You know the whole design of the opponent machine. One thing is missing: you do not know which state it starts in. Your machine still has to beat it in at least 99% of the first $10^9$ rounds. That is what we call an epic win.

Many machines reach that target, so this problem pins down one of them. Build your machine by the procedure below and print it.

Number the opponent states from 1 to $n$. Write $move(q)$ for the move shown in state $q$, and $next(q, x)$ for the opponent state reached from $q$ when you show $x$.

Separation distance. For an ordered pair $(a, b)$ of opponent states define $e(a, b)$ as follows. If $move(a) \ne move(b)$ then $e(a, b) = 1$. Otherwise $e(a, b) = 1 + \min_x e(next(a, x), next(b, x))$ over the three moves $x$. If no choice of your moves ever brings a round where the two states show different moves, then $e(a, b) = \infty$. Every pair with $a = b$ is $\infty$.

Candidate sets. A candidate set is a nonempty set of opponent states. Reduce a candidate set $B$ by this rule: if $e(a, b) = \infty$ for every two distinct $a, b \in B$, replace $B$ by the set holding only the smallest element of $B$, and otherwise keep $B$ unchanged. One reduced candidate set is one state of your machine.

The move shown in a reduced set $B$ is this.

1. If $B$ holds a single state, that is $B = \{q\}$, show the move that beats $move(q)$.
2. Otherwise take the pairs $(a, b)$ with $a < b$, both in $B$, and $e(a, b)$ finite, and pick the smallest one comparing $e(a, b)$ first, then $a$, then $b$. Going through Rock, Paper, Scissors in this order, show the first move $x$ that minimizes $e(next(a, x), next(b, x))$. Here $\infty$ counts as larger than every integer.

The transitions of $B$ are this. Let $x$ be the move chosen above and let $m$ be the observed opponent move. Put $B_m = \{q \in B : move(q) = m\}$. If $B_m$ is empty, the transition on $m$ goes to state 1. Otherwise it goes to the reduced form of $\{next(q, x) : q \in B_m\}$.

Number the states in this order. State 1 is the reduced form of the whole set $\{1, 2, \dots, n\}$. Handle the states from the smallest number upwards, and inside one state go through the observed moves in the order Rock, Paper, Scissors. Every time a set without a number shows up, give it the smallest free number. Equal sets always get the same number. Print the states in that order.

The first line has one integer $n$, the number of states of the opponent machine ($1 \le n \le 100$). States are numbered from 1 to $n$.

Each of the next $n$ lines describes one state. Line $i$ has a character $c_i$ and integers $r_i$, $p_i$, $s_i$. The character $c_i$ is R, P, or S and is the move shown in state $i$. The integers $r_i$, $p_i$, $s_i$ are the states the opponent moves to from state $i$ when you show Rock, Paper, or Scissors ($1 \le r_i, p_i, s_i \le n$).

On the first line print $k$, the number of states of your machine.

On each of the next $k$ lines print one state in the same format as the input: the move shown in that state as R, P, or S, then the states it moves to when the observed opponent move is Rock, Paper, or Scissors.

State 1 is the starting state of your machine. On every input of this problem the procedure above produces at most 50000 states.

Collect every opponent state that agrees with what you have observed through round $t$, and you get the current candidate set of your machine. The two differ only where indistinguishable states were folded into one. So once the candidate set holds a single state you know every move the opponent will show and you win every remaining round.

In each round either the candidate set gets smaller or the separation distance of the chosen pair drops by one. That distance never exceeds $n - 1$ and the set can shrink at most $n - 1$ times, so fewer than $n^2$ rounds are not won. That is far under 1% of $10^9$.