불균형 회피

왼쪽과 오른쪽 두 접시가 달린 특별한 양팔 저울이 있다. 처음에는 두 접시 모두 비어 있다. 무게가 1그램으로 모두 같은 구슬이 N개 들어 있는 상자도 있고, 구슬에는 1부터 N까지 번호가 붙어 있다.

이 저울은 매우 예민해서, 어느 순간이라도 왼쪽 접시의 총 무게와 오른쪽 접시의 총 무게가 1그램보다 크게 차이 나면 부서진다. 예를 들어 한쪽 접시에 구슬이 4개 있다면 다른 쪽 접시에는 구슬이 3개, 4개, 5개 중 하나만큼 있어야 한다.

친구 Libra가 저울을 한 번도 부수지 않고 다음 과정을 해내 보라고 도전장을 내밀었다.

• 먼저 구슬을 번호 순서대로 하나씩 저울에 올린다. 구슬 1, 구슬 2, 이런 식으로 구슬 N까지 올린다. 구슬마다 왼쪽 접시에 올릴지 오른쪽 접시에 올릴지 정한다.
• 그다음 친구가 정한 순서 A1, A2, ..., AN대로 구슬을 하나씩 저울에서 내린다. 이 순서는 1, 2, ..., N의 순열이며, i번째로 내리는 구슬은 번호가 Ai인 구슬이어야 한다.

이 과정을 해낼 방법을 찾아라.

첫째 줄에 테스트 케이스의 수 T가 주어지고, 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 구슬의 개수 N이 주어진다. 다음 줄에는 처음 N개의 자연수로 이루어진 순열 A1, A2, ..., AN이 주어진다. 구슬을 내리는 단계에서 i번째로 내리는 구슬은 번호가 Ai인 구슬이어야 한다.

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 길이가 N인 문자열이다. 이 문자열의 i번째 문자(1부터 센다)는 번호가 i인 구슬을 왼쪽 접시에 올리면 대문자 L, 오른쪽 접시에 올리면 대문자 R이다.

답이 적어도 하나 존재함이 보장된다. 가능한 답이 여러 개라면 그중 사전순으로 가장 앞선 문자열을 출력한다. 이때 L이 R보다 앞선다.

• 1 ≤ T ≤ 100
• 1 ≤ N
• 한 입력에 들어 있는 모든 테스트 케이스의 N의 합은 200,000 이하이다.
• 모든 i에 대해 1 ≤ Ai ≤ N
• i ≠ j인 모든 i, j에 대해 Ai ≠ Aj

예제의 첫 번째 테스트 케이스에서는 구슬 1을 왼쪽 접시에, 구슬 2를 오른쪽 접시에, 구슬 3을 오른쪽 접시에, 구슬 4를 왼쪽 접시에 올린다. 이 과정에서 (왼쪽, 오른쪽) 접시의 총 무게는 (1, 0), (1, 1), (1, 2), (2, 2)로 변하며, 차이가 한 번도 1을 넘지 않는다.

그다음 구슬을 3, 1, 2, 4 순서로 내려야 한다. 이때도 두 접시의 총 무게는 (2, 1), (1, 1), (1, 0), (0, 0)으로 변하며, 어느 순간에도 차이가 1을 넘지 않는다. 성공이다.

같은 이유로 두 접시를 맞바꾼 RLLR도 저울을 부수지 않지만, 사전순으로 LRRL이 더 앞서므로 LRRL을 출력한다.

다음은 이 테스트 케이스에서 저울을 부수는 답의 예다.

• LLRR: 구슬 2를 올릴 때 저울이 부서진다.
• LRLR: 구슬 1(두 번째로 내리는 구슬)을 내릴 때 저울이 부서진다.

N이 홀수인 예도 몇 가지 보자.

• 순서가 1이면 L과 R 모두 저울을 부수지 않으므로 L을 출력한다.
• 순서가 2 3 1이면 가능한 답은 LRR과 RLL뿐이므로 LRR을 출력한다. LLL, LLR, RRL, RRR은 구슬을 올리는 단계에서 저울을 부수고, LRL과 RLR은 구슬을 내리는 단계에서 저울을 부순다.