题目描述

小文正在玩一个有 $n$ 个关卡的游戏，初始拥有 $H$ 点体力。他必须按顺序通过所有关卡，每关恰好选择以下一种方式：

• 硬闯，记为 P：消耗 1 点体力，获得 1 枚金币。当前体力为 0 时不能选择硬闯。
• 使用技能，记为 S：不消耗体力，也不获得金币。使用技能后，接下来的 $k$ 个关卡不能再次使用技能。当 $k=0$ 时，可以在下一关继续使用技能。

请计算小文通过全部关卡最多能获得多少枚金币，并在所有获得最多金币的通关方案中，输出字典序最小的操作序列。比较字典序时，P 小于 S。

如果无法通过全部关卡，输出 -1。

输入格式

从文件 game.in 中读取数据。

输入一行，包含三个整数 $n,H,k$，分别表示关卡数、初始体力和技能冷却的关卡数。

输出格式

输出到文件 game.out 中。

如果无法通过全部关卡，输出一行 -1。

否则，第一行输出最多能获得的金币数；第二行输出一个长度为 $n$、仅由 P 和 S 组成的字符串，表示符合要求的操作序列。

样例

10 7 2

7
PPPSPPSPPS

10 5 2

-1

5 10 3

5
PPPPP

6 4 1

4
PPPSPS

数据规模与约定

对于所有数据，$1\le n\le10^7$，$0\le H\le10^9$，$0\le k\le10^7$。

本题共有 7 个子任务，采用子任务捆绑计分：只有通过某个子任务的全部测试数据，才能获得该子任务的分数。

下发文件

下载三组测试数据，非真实测试数据