#CSPS2021C. 回文 (Palindrome)

回文 (Palindrome)

Description

You are given a positive integer nn and a sequence of integers a1,a2,,a2na_1, a_2, \cdots, a_{2n}. The numbers 1,2,,n1, 2, \cdots, n each occur exactly twice in these 2n2n numbers. Create a sequence b1,b2,,b2nb_1, b_2, \cdots, b_{2n} of the same length 2n2n by performing 2n2n operations. Initially, bb is an empty sequence. One of the following two operations can be performed at a time:

  1. Add the first element of the sequence aa to the end of bb and remove it from aa.
  2. Add the last element of the sequence aa to the end of bb and remove it from aa.

The goal is to make bb a palindrome, i.e., for all 1in1 \le i \le n, bi=b2n+1ib_i = b_{2n + 1 - i} should be satisfied. Find whether this goal can be achieved, and if so, find the lexicographically smallest sequence of operations as described in the output format.

Input Format

The first line contains an integer TT denoting the number of test cases. The first line of each test case contains a positive integer nn and the second line contains 2n2n space-separated integers a1,a2,,a2na_1, a_2, \cdots, a_{2n}.

Output Format

Print one line for each test case. If a palindrome can't be generated, print 1-1. Otherwise, print a string of length 2n2n consisting of the characters LL and RR (without spaces), where LL represents operation 11 and RR represents operation 22. The string should be the lexicographically smallest among the strings corresponding to all the sequences of operations that achieve the goal. A string s1..2ns_{1..2n} is lexicographically smaller than t1..2nt_{1..2n} if and only if there exists a position 1k2n1 \le k \le 2n such that 1i<k\forall 1 \le i < k, si=tis_i = t_i and sk<tks_k < t_k.

2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3
LRRLLRRRRL
‐1

In the first test case, the generated sequence bb is 4 5 3 1 2 2 1 3 5 44\space 5\space 3\space 1\space 2\space 2\space 1\space 3\space 5\space 4. It can be seen that this is a palindrome. Another possible sequence of operations is LRRLLRRRRRLRRLLRRRRR, but it is lexicographically larger than the answer sequence.

Sample 2

See palin2.in and palin2.ans.

Constraints

Let n\sum n denote the sum of nn over all TT test cases. It is guaranteed that for each test file, 1T1001 \le T \le 100, 1n1 \le n, and n5×105\sum n \le 5 \times 10^5.

Tests TT nn n\sum n Special nature
171 \sim 7 10\le 10 50\le 50 No
8108 \sim 10 100\le 100 20\le 20 1000\le 1000
111211 \sim 12 100\le 100
131513 \sim 15 1000\le 1000 25000\le 25000
161716 \sim 17 =1= 1 5×105\le 5 \times 10^5
182018 \sim 20 100\le 100 Yes
212521 \sim 25 No

Special nature: If we delete two adjacent and equal numbers in aa at a time, there is a way to delete the entire sequence (e.g., a=[1,2,2,1]a = [1, 2, 2, 1]).