О нет!
Вас поймал коронавирус, и теперь вы сидите в тёмном подвале, связанные по ногам (но не по рукам). У вас есть вкусная печенька, а также перед вами стоит ноутбук, и там открыта ваша любимая среда разработки. Коронавирус убеждает вас решить следующую задачу.
Вам дано два массива \(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\).
Решите эту задачу, или коронавирус продлит карантин на пять лет и заставит всю экономику рухнуть!
Выходные данные
Если из массива \(A\) нельзя получить массив \(B\), в единственной строке выведите «IMPOSSIBLE» (без кавычек).
Если минимальное количество операций второго типа превышает \(2\cdot 10^5\), то в первой строке выведите «BIG» (без кавычек). Во второй строке выведите минимальное количество операций второго типа, которые нужно применить, чтобы из массива \(A\) получить \(B\).
Иначе, в первой строке выведите «SMALL» (без кавычек). Во второй строке выведите суммарное количество операций первого и второго типа \(m \le 5\cdot 10^5\) (гарантируется, что в этом случае существует такая последовательность действий). В третьей строке выведите строку длины \(m\), состоящую из символов «R» и «P» (без кавычек):
\(i\)-й символ должен быть равен 'R', если \(i\)-е действие первого типа, и должен быть равен 'P', иначе.
Если таких последовательностей несколько, выведите любую из них.
Вы можете выводить все символы как в нижнем регистре, так и в верхнем.
Примечание
В первом примере массивы \(A\) и \(B\) уже совпадает, поэтому количество нужных операций \(=0\).
Во втором примере надо \(299999\) раз заменить \(A\) на префиксную сумму, а потом развернуть массив. Так как \(299999>2\cdot 10^5\), то восстанавливать ответ не нужно.
В четвёртом примере из массива \(A\) никак нельзя получить \(B\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 7
5 7
|
SMALL
0
|
|
2
|
2
1 1
300000 1
|
BIG
299999
|
|
3
|
2
10 1
13 14
|
SMALL
6
RPPPRP
|
|
4
|
3
1 2 1
2 1 2
|
IMPOSSIBLE
|