Maximizing the reward
You are given N tasks with following information:

Deadline: Di
Reward: Ri
Time taken to complete the tasks: Pi

The reward is given only when a task is completed within the corresponding deadline.
Write a program to schedule the tasks in order to maximize the reward.

Input format
First line: T (number of test cases)
First line in each test case: N
Next N lines in each test case: Three space-separated integers Di, Ri, and Pi

Output format
For each test case, print the schedule of tasks that maximizes the reward in new line.

Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 10^3
1 ≤ D ≤ 10^3
1≤P≤D
1 ≤ R ≤ 10^6

Sample Input
1
6
1 2 1
2 3 1
4 1 2
10 10 10
15 13 10
15 7 5

Sample Output
20

Explanation
If we perform the last two task alone we can get the maximum reward which is 20.
Note: Your code should be able to convert the sample input into the sample output. However, this is not enough to pass the challenge, because the code will be run on multiple test cases. Therefore, your code must solve this problem statement.

RescueOps
After years of research and development, Bob has succeeded in creating a robot which can move according to his remote commands. The robot is still in its prototype stage, so it can only perform 3 kinds of operations, L (turn left), R (turn right) and M (move one step forward). However on its maiden trip on the grid, the robot crashed after a few operations. Now, Bob has to reach his robot at the earliest, before anyone else captures it. So he needs to reach it in minimum number of steps. Unlike his robot, Bob can move in all 8 cardinal directions. You are required to output the path of minimum length in terms of the numbering given on the cardinal directions. Also append a 0 at the end to indicate that the destination is reached.

Input:

First line contains T which is the number of test cases. Each test case contains 2 lines. First line of every test case contains an integer N where N is the number of commands before the robot crashed.Second line of every test case contains the N commands as a string.

Output:
For each test case, output the resultant operation code required according to given rules.

Constraints:
1≤T≤10
1≤N≤10^5
Scoring:
1≤N≤10:(30pts)
1≤N≤1000:(30pts)
Original Constraints : (40pts)

Note: In case there are multiple paths of same length, you are to output the lexicographically smallest of them.
SAMPLE INPUT
2
4
MMLM
6
LMRMLM

SAMPLE OUTPUT
450 480

Explanation
Case 1: He moves 2 steps North, then turns left and moves one step towards west. So if initial position is (0,0) his final position is (-1,2). He can reach this is multiple ways: (NORTH, NORTH, WEST) or (WEST,NORTH, NORTH) or (NORTH, NORTHWEST). But the path which gives lexicographically smallest string, is (NORTHWEST, NORTH).
Case 2: The final position is (-2,1).