小P最近迷上了石头剪刀布，他观看了一场沙雕石头剪刀布大赛

比赛共有 $2^n$ 个沙雕参加， 分为 $n$ 轮，在每轮中，第 $0$ 位选手和第 $1$ 位选手对战，胜者作为新的第 $0$ 位选手，第 $2$ 位和第 $3$ 位对战，胜者作为新的第 $1$ 位选手，以此类推。

小P得知，每个沙雕都有一种固定的偏爱决策，每个沙雕在每一次对战中都只会使用他的偏爱决策。

如果一次对战的双方的偏爱决策相同，那么这次对战就永远不会结束，那么作为观众会十分无聊。

现在，小P知道了偏爱每种决策的沙雕数目，他想知道一种能够决出最终胜负的初始的次序。

若有多种可能次序，我们设字典序最小的为答案。

因为答案可能很长，你只需要输出答案的$hash$值以及第$l$到$r$位。

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

($S_i$表示初始标号为$i$的人的偏好决策对应的大写字母 ASCII 码)

输入格式

第一行两个整数$n, op$，表示数据规模和数据类型。

第二行一个大整数，表示偏爱决策为石头$R$的人数。

第三行一个大整数，表示偏爱决策为剪刀$S$的人数。

第四行一个大整数，表示偏爱决策为布$P$的人数。

若$op\neq 1$，第五，六行，两个$n$位二进制数$l,r$，表示要求你输出的范围。

输出格式

若不存在合法初始序列，输出-1，否则：

若$op\neq 2$，输出一个整数，表示最优序列$hash$值。

若$op\neq 1$，输出一个由$"R,S,P"$构成的字符串，表示最优序列的第$l$到$r$位。

样例一

input

4 3
4
4
8
0000
1111

output

-1

样例二

input

1 1
1
1
0

output

19421

样例三

input

2 2
1
2
1
01
10

output

SR

样例四

input

3 3
2
3
3
011
110

output

879001374
SPSR

样例五至样例六

见样例数据下载。

限制与约定

本题采用捆绑测试。

对于所有子任务均满足 $1\ \leq\ n\ \leq\ 300000,\ 0\leq\ r-l\leq\ 300000 ,\ R+S+P=2^n$。

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$

下载

样例数据下载