Assimilation

Time limit1sMemory limit128 MB

Summary

Two players alternately flip one connected region of the rival color on a board of up to 5 by 5, and the player whose color fills the board wins.

Level: Hard8 of 10
Topics: Game theory, Graph, Brute force
Solved: No attempts yet

Problem

Farmer Brown's farm is a grid of $r \times c$ paddocks. Each paddock holds either rabbits or sheep.

Two malicious genies play a game on the farm. GEnie R picks a paddock that holds sheep and turns those sheep into rabbits. The change spreads sideways. Sheep in a paddock sharing an edge with it also become rabbits, then the sheep next to those become rabbits as well. In one turn the whole block of sheep joined to the chosen paddock through shared edges becomes rabbits. GEnie S does the opposite, picking a paddock of rabbits and turning the whole joined block of rabbits into sheep.

The genies move alternately. The moment every paddock holds the same kind of animal, the genie that owns that animal wins. If the farm already holds one kind of animal before anyone moves, that genie has already won. Both genies are very clever, so if one of them has a winning strategy then it will be used.

Given the genie that moves first and the starting layout, determine the winner. One side always wins.

For example, suppose GEnie R moves first and the starting layout is

RSR
RSS
SRR

GEnie R has two moves.

RRR    RSR
RRR    RSS
SRR    RRR

After the left move the remaining rabbits form one block, so GEnie S turns all of them into sheep on the next turn and wins. After the right move, whether GEnie S takes the block of rabbits in the lower left or the single rabbit paddock in the upper right, one block of sheep is left and GEnie R wins on the next turn. So in this layout GEnie R has a winning strategy.

Input

The input holds several games. The first line of each game has the number of rows $r$ and the number of columns $c$ of paddocks, then one upper case letter naming the genie that moves first, separated by spaces. The values satisfy $1 \le r, c \le 5$ , and the letter is R or S.

The next $r$ lines each hold a string of length $c$ made only of R and S. R is a paddock of rabbits and S is a paddock of sheep.

The last line is 0 0 # and is not part of any game.

Output

For each game print one character on its own line naming the winning genie. Print R if GEnie R wins and S if GEnie S wins.

Examples2

Example 1
Input
```
1 3 S
RSR
3 3 R
RSR
RSS
SRR
0 0 #
```
Expected output
```
R
R
```

Example 2

Input

1 1 R
R
1 1 S
R
1 1 S
S
1 1 R
S
0 0 #

Expected output

R
R
S
S