問題文

長さ $N−1$ の整数列 $A=(A_1,\ldots,A_{N-1})$ が与えられます。

R,P,S のみからなる文字列 $S$ について $f(S)$ を以下のように定義します。

操作

• $i=1,2,\ldots,N-1$ の順に $N-1$ 回の操作を行う
  • $S_{A_i} = S_{A_{i}+1}$ のとき、操作を中断する
  • そうでないとき、$S_{A_i}$ と $S_{A_i+1}$ はじゃんけんで勝敗が決まる。負ける方を取り除く
    • R と P では R が負ける
    • P と S では P が負ける
    • S と R では S が負ける
• $N-1$ 回の操作を行った後の文字列を $f(S)$ とする

$A$ の制約により、適切に文字列 $S$ を選べば $N-1$ 回の操作が行えることが保証されます。

$f(S)=$R,P,S となるような文字列 $S$ のうち辞書順で $K$ 番目に小さいものをそれぞれ求めてください。 そのような文字列が存在しない場合はそれを報告してください。

$T$ 個のテストケースが与えられるので、各テストケースについて上記の問題を解いてください。

制約

• $1 \le T \le 10^5$
• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le N- i\ (1 \le i \le N-1)$
• $1 \le K \le 10^{18}$
• $1$ つのファイルにおいて全てのテストケースにおける $N$ の合計は $2 \times 10^5$ 以下
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ここで $\text{case}_i$ は $i$ 番目のテストケースを表す。

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

各テストケースは $2$ 行からなり、以下の形式で与えられる。

$N$ $K$
$A_1 A_2 \dots A_{N-1}$

出力

テストケースごとに以下のように $3$ 行出力せよ。

• $1$ 行目に $f(S)=$R となるような文字列 $S$ のうち辞書順で $K$ 番目に小さいものが存在するならばそれを出力せよ。存在しないならば -1 を出力せよ。
• $2$ 行目に $f(S)=$P となるような文字列 $S$ のうち辞書順で $K$ 番目に小さいものが存在するならばそれを出力せよ。存在しないならば -1 を出力せよ。
• $3$ 行目に $f(S)=$S となるような文字列 $S$ のうち辞書順で $K$ 番目に小さいものが存在するならばそれを出力せよ。存在しないならば -1 を出力せよ。

サンプル

3
5 1
4 2 2 1
5 3
4 2 2 1
7 10000
6 2 2 1 1 1

RPRPS
PPSRS
PPRPS
RPSPR
PRSPS
PPSPR
-1
-1
-1