Tasty Cookie
Contest: Codeforces Round 645 (Div. 2)
Difficulty rating: 2700
Tags: binary search, constructive algorithms, greedy, implementation

Oh, no!

The coronavirus has caught you, and now you're sitting in a dark cellar, with tied legs (but not hands). You have a delicious cookie, a laptop in front of you, and your ideal development environment is open. The coronavirus convinces you to solve the following problem.

You are given two arrays $$$A$$$ and $$$B$$$ of size $$$n$$$. You can do operations of two types with array $$$A$$$:

- Reverse array $$$A$$$. That is the array $$$[A_1,\ A_2,\ \ldots,\ A_n]$$$ transformes into $$$[A_n,\ A_{n-1},\ \ldots,\ A_1]$$$.
- Replace $$$A$$$ with an array of its prefix sums. That is, the array $$$[A_1,\ A_2,\ \ldots,\ A_n]$$$ goes to $$$[A_1,\ (A_1+A_2),\ \ldots,\ (A_1+A_2+\ldots+A_n)]$$$.

You need to understand if you can get an array $$$B$$$ from the array $$$A$$$. If it is possible, you will have to restore the order of these operations by minimizing the number of operations of the second type. Fortunately, the coronavirus is good today, so he has allowed you not to restore actions if the minimum number of second type operations is more than $$$2\cdot 10^5$$$. But coronavirus resents you, so if you restore the answer, the total number of operations should not exceed $$$5\cdot 10^5$$$.

Solve this problem and get the cookie, or the coronavirus will extend the quarantine for five years and make the whole economy collapse!

Input format:
The first line contains a single integer $$$n$$$ ($$$1\le n \le 2\cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$A_1, A_2, \ldots, A_n$$$ ($$$1 \le A_i \le 10 ^ {12}$$$).

The third line contains $$$n$$$ integers $$$B_1, B_2, \ldots, B_n$$$ ($$$1 \le B_i \le 10 ^ {12}$$$).

Output format:
If you cannot get $$$B$$$ from the $$$A$$$ array, print "IMPOSSIBLE" (without quotes) on a single line.

If the minimum number of operations of the second type exceeds $$$2\cdot 10^5$$$, print "BIG" (without quotes). In the second line print the number of operations of the second type, that needs to be applied to get array $$$B$$$ from $$$A$$$.

Otherwise, in the first line print "SMALL" (without quotes). In the second line print the total number of operations of the first and second types $$$m \le 5\cdot 10^5$$$ (it is guaranteed that in this case there is such a sequence of actions). In the third line print a line of length $$$m$$$, consisting of characters 'R"and 'P' (without quotes).

The $$$i$$$-th character should be 'R', if the $$$i$$$-th action is of the first type, and should be 'P', otherwise.

If there are several such sequences, you can print any of them.

You can print each character in the uppercase or in the lowercase.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example, the arrays $$$A$$$ and $$$B$$$ already equal, so the number of required operations $$$=0$$$.

In the second example, we need to replace $$$A$$$ with the prefix sums $$$299999$$$ times and then reverse the array. Since $$$299999>2\cdot 10^5$$$, there is no need to restore the answer.

In the fourth example, you cannot get $$$B$$$ from the $$$A$$$.

Example input:
2
5 7
5 7

Example output:
SMALL
0

Example input:
2
1 1
300000 1

Example output:
BIG
299999

Editorial:
Let's define a few operations and constants:
• $$$pref$$$ — replace an array with its prefix sums array
• $$$reverse$$$ — reverse an array
• $$$rollback$$$ — restore the original array from a prefix sums array
• $$$C$$$ — the array values upper bound — $$$10^{12}$$$
First, we can prove that $$$rollback$$$ is unambiguosly defined for strictly increasing arrays. Consider an array $$$X$$$. Let $$$Y$$$ be the prefix sums array of $$$X$$$. Notice that $$$X_0 = Y_0$$$, $$$X_i = Y_i - Y_{i - 1}$$$ (for $$$i>1$$$). Thus we can restore $$$X$$$ from $$$Y$$$. Note that if we apply $$$rollback$$$ to an array for which $$$Y_i > Y_{i - 1}$$$ doesn't hold, the resulting array will have a non-positive element which is forbidden by the statements.
Now let's analyze how many $$$pref$$$ operations can theoretically be applied for arrays of different lengths (let's call their count $$$t$$$) (We can do that by applying $$$pref$$$ to array $$$[1, 1, ..., 1]$$$ while all numbers are below $$$C$$$):

It's obvious that we'll need no more than $$$t$$$ $$$rollback$$$s for an array of length $$$n$$$. It can also be proved that $$$t = \mathcal{O}(\sqrt[n-1]{C\cdot(n-1)!})$$$.
Let's restore the array $$$B$$$ in steps. One each step we have several cases:
• If $$$B$$$ equals $$$A$$$ or $$$reverse(A)$$$, we know how to get $$$A$$$ from $$$B$$$.
• If $$$B$$$ is strictly increasing, apply $$$rollback$$$.
• If $$$B$$$ is strictly decreasing, apply $$$reverse$$$.
• Otherwise, the answer is "$$$impossible$$$".
This solution will run infinitely when $$$n=1$$$ and $$$A \ne B$$$, so the case when $$$n=1$$$ has to be handled separately.
The asymptotic of this solution is $$$\mathcal{O}(n\cdot ans)$$$. Notice that $$$ans \le 2t+1$$$ because we can't have two $$$reverse$$$ operations in a row. It means this solution will fit into TL for $$$n \ge 3$$$, but we need a separate solution for $$$n=2$$$.
Consider an array $$$[x, y]$$$. If we $$$rollback$$$ it while $$$x<y$$$, the array will be transformed into $$$[x, y \mod x]$$$. It means we can $$$rollback$$$ several iterations at once.
So, the solution for $$$n=2$$$ is:
• First sort $$$A$$$ and $$$B$$$ so that they both increase (and take this into account when printing answer)
• Now start the $$$rollback$$$ loop:   If $$$B_1=A_1$$$, we can break the loop if $$$(B_2 - A_2) \mod B_1=0$$$, otherwise the answer is "$$$impossible$$$".  If $$$B_1 \ne A_1$$$, we can calculate how many $$$rollback$$$ operations we should apply to transform $$$B=[x, y]$$$ into $$$[x, y \mod x]$$$, modify the answer accordingly and jump to the next iteration for $$$B=[y \mod x, x]$$$ (after applying one $$$reverse$$$ operation).
• If $$$B_1=A_1$$$, we can break the loop if $$$(B_2 - A_2) \mod B_1=0$$$, otherwise the answer is "$$$impossible$$$".
• If $$$B_1 \ne A_1$$$, we can calculate how many $$$rollback$$$ operations we should apply to transform $$$B=[x, y]$$$ into $$$[x, y \mod x]$$$, modify the answer accordingly and jump to the next iteration for $$$B=[y \mod x, x]$$$ (after applying one $$$reverse$$$ operation).
This algorithm is very similar to the Euclidian's algorithm, and that's how we can prove there will be $$$\mathcal{O}(\log C)$$$ $$$rollback$$$s.
The overall complexity is $$$\mathcal{O}(n\cdot ans)$$$ for $$$n>2$$$;  $$$\mathcal{O}(\log C)$$$ for $$$n=2$$$.