Little P has recently become obsessed with Rock Paper Scissors, and he watched a silly Rock Paper Scissors tournament.

The tournament has $2^n$ participants and consists of $n$ rounds. In each round, the participant at index $0$ plays against the participant at index $1$, the winner becomes the new participant at index $0$; the participant at index $2$ plays against the participant at index $3$, the winner becomes the new participant at index $1$, and so on.

Little P learned that every participant has a fixed preferred move, and each participant will only use their preferred move in every match they play.

If the preferred moves of both participants in a match are the same, the match will never end, which would be very boring for the audience.

Now, Little P knows the number of participants who prefer each move. He wants to find an initial ordering of participants that allows a final winner to be determined.

If there are multiple possible orderings, we define the one that is lexicographically smallest as the answer.

Since the answer can be very long, you only need to output the $hash$ value of the answer and the characters from index $l$ to $r$.

$$hash=\sum_{i=0}^{2^n-1}S_i \times 233^i \bmod998244353$$

($S_i$ represents the ASCII code of the uppercase letter corresponding to the preferred move of the person at initial index $i$)

Input

The first line contains two integers $n$ and $op$, representing the data scale and the data type.

The second line contains a large integer representing the number of people whose preferred move is Rock ($R$).

The third line contains a large integer representing the number of people whose preferred move is Scissors ($S$).

The fourth line contains a large integer representing the number of people whose preferred move is Paper ($P$).

If $op \neq 1$, the fifth and sixth lines contain two $n$-bit binary numbers $l$ and $r$, representing the range you are required to output.

Output

If no valid initial sequence exists, output -1. Otherwise:

If $op \neq 2$, output an integer representing the $hash$ value of the optimal sequence.

If $op \neq 1$, output a string consisting of "R", "S", and "P", representing the characters of the optimal sequence from index $l$ to $r$.

Examples

Input 1

4 3
4
4
8
0000
1111

Output 1

-1

Input 2

1 1
1
1
0

Output 2

19421

Input 3

2 2
1
2
1
01
10

Output 3

SR

Input 4

3 3
2
3
3
011
110

Output 4

879001374
SPSR

Constraints

This problem uses bundled testing.

For all subtasks, $1 \leq n \leq 300000$, $0 \leq r-l \leq 300000$, and $R+S+P=2^n$.