Problem Description

Given a positive integer $n$ and an integer sequence $a_1, a_2, \ldots, a_{2 n}$, among these $2 n$ numbers, each of $1, 2, \ldots, n$ appears exactly $2$ times. Now perform $2 n$ operations, with the goal of creating a sequence $b_1, b_2, \ldots, b_{2 n}$ of the same length $2 n$. Initially, $b$ is an empty sequence. Each time, you may perform one of the following two operations:

1. Append the first element of sequence $a$ to the end of $b$, and remove it from $a$.
2. Append the last element of sequence $a$ to the end of $b$, and remove it from $a$.

Our goal is to make $b$ a palindromic sequence, that is, it satisfies for all $1 \le i \le n$, $b_i = b_{2 n + 1 - i}$. Please determine whether this goal can be achieved. If it can, output the lexicographically smallest operation plan, as explained in Output Format.

Input Format

Each test point contains multiple groups of testdata.

The first line of input contains an integer $T$, the number of test cases. For each test case:

The first line contains a positive integer $n$.
The second line contains $2 n$ space-separated integers $a_1, a_2, \ldots, a_{2 n}$.

Output Format

For each test case, output one line as the answer.

If it is impossible to generate a palindromic sequence, output a line -1. Otherwise, output a string of length $2 n$ consisting of characters L or R (with no spaces), where L means removing the first element (operation 1), and R means operation 2.

You need to output the lexicographically smallest string among all valid plans.

The lexicographical order is defined as follows: for two strings $s_{1 \sim 2 n}$ and $t_{1 \sim 2 n}$ of length $2 n$, $s$ is lexicographically smaller than $t$ if and only if there exists an index $1 \le k \le 2 n$ such that for every $1 \le i < k$, $s_i = t_i$, and $s_k < t_k$.

2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3

LRRLLRRRRL
-1

见附件中的 palin/palin2.in

见附件中的 palin/palin2.ans

Hint

Sample Explanation #1

In the first group of data, the generated sequence $b$ is $[4, 5, 3, 1, 2, 2, 1, 3, 5, 4]$, and you can see that this is a palindromic sequence.

Another possible operation plan is LRRLLRRRRR, but its lexicographical order is larger than the answer.

Constraints

Let $\sum n$ denote the sum of $n$ over all $T$ test cases.

For all test points, it is guaranteed that $1 \le T \le 100$, $1 \le n, \sum n \le 5 \times {10}^5$.

Special Property: If each time we delete two adjacent equal numbers in $a$, there exists a way to delete the entire sequence (for example, $a = [1, 2, 2, 1]$).

Hack testdata provided by
@潜在了H2O下面。

Translated by ChatGPT 5