PE class - Team Arrangement Problem · IZhO 2024 #A
Physics · mechanics
Problem
Dimash is a physical education teacher at a school. At the moment, he is conducting a class with 2⋅n students. They are going to play a certain game with 2 teams and each team should have n students.
Before the game, Dimash lined up all 2⋅n students in a row, dressing the participants of the first team in red T-shirts and the participants of the second team in blue T-shirts. Then, each student in a red T-shirt looked to the left and counted the difference between the number of students of his color and the number of students of the opposite color. Similarly, each student in a blue T-shirt looked to the right and counted the difference between the number of students of his color and the number of students of the opposite color. Note that the difference is calculated with a sign and can be either a positive or a negative number.
All the students, from left to right, spoke out their calculated numbers. Dimash recorded all the numbers in a list, but in a shuffled order. Find, based on the record, any suitable arrangement of students that could have been at Dimash's disposal. If there are multiple suitable answers, output any of them.
Input:
The first line contains a single integer t(1≤t≤3⋅105) — the number of test cases. Then follows the description of the test cases.
The first line of each test case contains a single integer n(1≤n≤3⋅105) — the number of students in each team.
The second line of each test case contains 2⋅n integers a1,a2,…,a2n(−n≤ai≤n) — the list of Dimash.
It is guaranteed that the sum of n for all test cases does not exceed 3⋅105.
It is guaranteed that the given list of Dimash is correct, meaning that the answer always exists.
Output:
For each test case, output a string of 2⋅n characters, where the i-th character is equal to 'L', if the i-th student in the row is in a red shirt and looking to the left, or 'R', if in a blue shirt and looking to the right.