← 返回题目列表

Codeforces · 1358/F

F. 美味饼干

中文机器翻译题面 查看原题

哦,不!

冠状病毒感染了你,现在你坐在黑暗的地窖里,双腿被绑着(但手没有被绑住)。你有一块美味的饼干,你面前有一台笔记本电脑,你理想的开发环境是开放的。冠状病毒说服您解决以下问题。

给定两个数组 $$$A$$$ 和 $$$B$$$,大小为 $$$n$$$。您可以对数组 $$$A$$$ 执行两种类型的操作:

- 反转数组$$$A$$$。即数组 $$$[A_1,\ A_2,\ \ldots,\ A_n]$$$ 转换为 $$$[A_n,\ A_{n-1},\ \ldots,\ A_1]$$$。
- 将 $$$A$$$ 替换为其前缀和的数组。也就是说,数组 $$$[A_1,\ A_2,\ \ldots,\ A_n]$$$ 转到 $$$[A_1,\ (A_1+A_2),\ \ldots,\ (A_1+A_2+\ldots+A_n)]$$$。

你需要了解是否可以从数组$$$A$$$中获取数组$$$B$$$。如果可能的话,您必须通过最小化第二类操作的数量来恢复这些操作的顺序。幸运的是,今天冠状病毒很好,所以他允许你在第二类操作的最小数量超过 $$$2\cdot 10^5$$$ 的情况下不恢复操作。但冠状病毒对你很反感,所以如果你还原答案,总的操作次数不应超过$$$5\cdot 10^5$$$。

解决这个问题并获得cookie,否则冠状病毒将隔离延长五年并使整个经济崩溃!

输入

第一行包含一个整数 $$$n$$$ ($$$1\le n \le 2\cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$A_1, A_2, \ldots, A_n$$$ ($$$1 \le A_i \le 10 ^ {12}$$$)。

第三行包含 $$$n$$$ 整数 $$$B_1, B_2, \ldots, B_n$$$ ($$$1 \le B_i \le 10 ^ {12}$$$)。

输出

如果无法从 $$$A$$$ 数组中获取 $$$B$$$,请在单行上打印“IMPOSSIBLE”(不带引号)。

如果第二类操作的最小数量超过$$$2\cdot 10^5$$$,则打印“BIG”(不带引号)。在第二行中打印第二种类型的操作数,需要应用该操作来从 $$$A$$$ 获取数组 $$$B$$$。

否则,在第一行打印“SMALL”(不带引号)。在第二行中打印第一种和第二种类型的操作总数 $$$m \le 5\cdot 10^5$$$ (保证在这种情况下存在这样的操作序列)。在第三行中打印长度为 $$$m$$$ 的行,由字符“R”和“P”(不带引号)组成。

如果第 $$$i$$$ 个动作属于第一类型,则第 $$$i$$$ 个字符应为“R”,否则应为“P”。

如果有多个这样的序列,您可以打印其中任何一个。

您可以以大写或小写形式打印每个字符。

示例

输入 #1

2
5 7
5 7

输出 #1

SMALL
0

输入 #2

2
1 1
300000 1

输出 #2

BIG
299999

输入 #3

2
10 1
13 14

输出 #3

SMALL
6
RPPPRP

输入#4

3
1 2 1
2 1 2

输出#4

IMPOSSIBLE

注意

在第一个示例中,数组 $$$A$$$ 和 $$$B$$$ 已经相等,因此所需操作的数量 $$$=0$$$。

在第二个示例中,我们需要将 $$$A$$$ 替换为前缀 sums $$$299999$$$ 次,然后反转数组。由于 $$$299999>2\cdot 10^5$$$,因此无需恢复答案。

在第四个示例中,您无法从 $$$A$$$ 获取 $$$B$$$。