Magnet Ring Reconstruction

There are n magnets arranged in a ring. Each magnet has a magnetic force given by \(4^{a_i}\) (the exponent \(a_i\) can be chosen arbitrarily), and the length of each magnet is exactly 1 unit. When the magnets are placed, each one can be oriented so that its north pole faces either left or right. For every adjacent pair of magnets, the magnitudes of their magnetic forces must be different.

The interaction between two adjacent magnets depends on their orientations. Suppose the two magnets are A and B which touch each other. If A is oriented left then its right end is its south pole; if A is oriented right then its right end is its north pole. Similarly, if B is oriented left then its left end is its north pole; if B is oriented right then its left end is its south pole. When the two magnets interact:

• If the contacting poles are opposite (i.e. (L,L) or (R,R) giving south–north), then they attract and will be placed touching (distance 0 between them).
• If the contacting poles are the same ((L,R) or (R,L)), then they repel and the distance between their magnets will equal \(4^{a_i}+4^{a_j}\) (if their forces are \(4^{a_i}\) and \(4^{a_j}\) resp.).

In the initial configuration the entire ring has a total length of \(d_0\) units. This value includes the unit lengths of all the magnets plus the distances between every adjacent pair according to the repulsive interactions (attractive pairs contribute 0 distance). In addition, for each magnet \(i\) (\(1 \le i \le n\)), if that magnet is removed and the remaining magnets reconnect in a ring (keeping their original orientations), then the new total ring length is measured as \(d_i\) units.

Your task is: Given \(n\), \(d_0\) and \(d_1, d_2,\dots,d_n\) (data is guaranteed to be consistent with some valid arrangement), construct any valid configuration of the magnets (that is, choose the exponents \(a_i\) and their orientations) so that when the ring’s length is computed according to the rules above the values match the input data. Note that the forces you assign must satisfy the condition that any two adjacent magnets have different magnetic force magnitudes.

For the purpose of this problem, you are free to choose the exponents \(a_i\) arbitrarily provided that \(4^{a_i}\) is the force for the i-th magnet and adjacent ones are different. (It is guaranteed that the input data always has at least one solution.)

---

Important note on the evaluation:

It turns out that one very simple valid configuration is obtained by making every pair of adjacent magnets attract. (Recall: if two magnets attract, they stick with no inter‐magnet gap.) If every adjacent pair attracts then the total ring length is \(n\) and, after removing any magnet, the ring length is \(n-1\). Thus, if the input data satisfies \(d_0=n\) and \(d_i=n-1\) for all \(1\le i\le n\), you may output the following trivial configuration:

• Set \(a_i=i-1\) for \(1\le i\le n\) (or any sequence so that adjacent forces \(4^{a_i}\) are distinct).
• Set every magnet’s orientation to be R (so that every adjacent pair is \(R, R\) and thus attract).

Since the input is guaranteed to be consistent with some configuration, your program may simply check whether \(d_0=n\) and \(d_i=n-1\) for all \(i\) and, if so, output the trivial configuration. (For other data, any valid configuration is acceptable.)

inputFormat

The first line contains a single integer \(n\) (\(3 \le n \le 10^5\)).

The second line contains one integer \(d_0\) \( (1 \le d_0 \le 10^{18})\) representing the total ring length with all magnets.

The next \(n\) lines each contain one integer \(d_i\) (\(1 \le d_i \le 10^{18}\)) for \(i=1,2,\dots,n\), where \(d_i\) is the ring’s length after the \(i\)-th magnet is removed.

Note: The input data is guaranteed to be consistent with some valid configuration.

outputFormat

Output your configuration in two lines:

• The first line contains \(n\) non‐negative integers \(a_1,a_2,\dots,a_n\) separated by spaces. These exponents define the magnetic force of each magnet as \(4^{a_i}\). It is required that for each adjacent pair \(i\) and \(i+1\) (and also for magnet \(n\) and magnet \(1\)) we have \(4^{a_i} \neq 4^{a_{i+1}}\).
• The second line contains a string of \(n\) characters. Each character is either L or R, representing the orientation of the corresponding magnet (where L means north facing left and R means north facing right).

The configuration must be such that when the ring length is computed using the rules (unit magnet lengths plus distances between adjacent magnets as defined by their magnetic interactions), the full ring length is \(d_0\) and after removing the \(i\)-th magnet the ring length becomes \(d_i\) for each \(i\). If multiple answers exist, any one is acceptable.

---

Scoring: Your solution will be tested against several test cases. Each test case specifies a score, and your program must produce a valid configuration for all test cases to be accepted.

sample

3
3
2
2
2

0 1 2
RRR

</p>