No.3673 Predicting the Future
Note: The execution time limit for this problem is set very strictly.
Problem Statement
You are playing a special version of rock-paper-scissors with a robot named Alice.
This game has 4 types of hands: R, S, P, and X. The outcome for your hand against Alice's hand is determined by the following table.
The rows of the table represent your hand, and the columns represent Alice's hand.
| Your hand / Alice's hand | R |
S |
P |
X |
|---|---|---|---|---|
R |
Draw | Win | Draw | Lose |
S |
Lose | Draw | Win | Draw |
P |
Draw | Lose | Draw | Win |
X |
Win | Draw | Lose | Draw |
Therefore, to beat Alice's hand, you need to play the following hand.
| Alice's hand | Winning hand |
|---|---|
R |
X |
S |
R |
P |
S |
X |
P |
Alice internally holds an unsigned 32-bit integer state.
Initially, state is chosen from the integers between $1$ and $2^{32}-1$, inclusive. You do not know this initial value.
In each round of the game, Alice executes the following pseudocode once to determine her hand.
state ← 1 以上 2^32-1 以下の整数から1つ選ぶ
function generate_random_number():
state ← state XOR (state << 13)
state ← state XOR (state >> 17)
state ← state XOR (state << 5)
return state
function choose_hand():
x ← generate_random_number()
if x mod 4 = 0:
return 'R'
else if x mod 4 = 1:
return 'S'
else if x mod 4 = 2:
return 'P'
else:
return 'X'
Here, XOR denotes bitwise exclusive OR, << denotes a left bit shift, and >> denotes a right bit shift.
All operations are performed on unsigned 32-bit integers. If the result of an operation exceeds 32 bits, the excess upper bits are truncated.
You have played $100$ rounds with Alice so far and recorded every hand she played.
This record is represented by a string $T$ of length $100$. The $i$-th character of $T$ represents the hand Alice played in the $i$-th round.
Use this record to win all of the upcoming $N$ rounds.
Formally, output a string $U$ of length $N$ satisfying the following conditions.
- $U_i$ represents the hand you play in round $100+i$.
- For all $1\leq i\leq N$, $U_i$ beats the hand Alice plays in round $100+i$.
It can be proved that, under the constraints of this problem, different initial states never generate the same string $T$.
Input
The input is given from standard input in the following format.
$T$ $N$
- $T$ is a string of length $100$
- Each character of $T$ is one of
R,S,P,X - $T$ is generated by the pseudocode in the problem statement
- $1\leq N\leq 2\times10^5$
- $N$ is an integer
Output
Output the answer on $1$ line. End the output with a newline.
Sample
Sample 1
Input
SSSXSRPPSRXXPPSSRRSSXSXXPSSRXPXRSRRRPPPXSPXXXSSRSSXXRSRRRRXSSPRXRRRPSRPSRRRSPSXRSRPRRRXXSXRSXSRPXSRX 1
Output
X
Sample 2
Input
XXXPSRRXPXXRRRPSXPRRRPSSRSXRSPSPXPPSSRRRXPSXSRRXRXSPXXRPPSSPSRPPPXSRSPRPSRXRSSPSRPSRPPRSPRSRSSXXPPXS 5
Output
PXSPR
Sample 3
Input
SXRRRSSSXSRRRSPSPSSRXPRSPSRSRXPRXSRXRPPPPPSSSRPSSRSRSXRRPPXRRSRXXSRSXXXXRPPRRSPSRSRXXSRPPXSRPSPPSRPR 10
Output
RPSRXPPSXP
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
harurun