The program must produce output for all test cases within the stipulated time)

A spaceship carrying a convention of high ranking officials had a close shave with a meteor. They are now scattered over the surface over a meteor and the spaceship is beyond repair.

Fluke LandCrawler was an emergency replacement for a space rescue mission in the distant galaxy Alfa-Bentauri. You are KHAL – the computer on the land-Rover carrying Fluke. He needs to rescue as many survivors as possible but can’t figure out the best path. Fluke lied about his CompSc. Degree to get in to SpaceTravel Inc; he is banking on you to save his job.

Just to make things worse, Fluke’s shuttle was designed by Elbonians and not tested before being deployed due to this unforeseen emergency. You now find that the “Back”, “Left”, “Right” and “Fwd” buttons on the shuttle are unintuitive to say the least:

e.g. if Fluke’s Rover is in the slot marked as FL below  (facing east), there are 4 possible slots that he can move to (shown in Blue). In short, it can not move back (towards the west) and is always facing east. He can only rescue people by moving to the slot that they are standing in.

Each survivor of the crash has a rank R (1<= R <= 5) e.g. some are Chancellors Rank5 and at the other end of the spectrum are Guards Rank1.

Determine the optimal path – that can

-          save a group of people with the maximum total rank. High ranking officials are key to maintaining peace across various factions in the federation. Guards are sworn to protect them and will stay behind if required.

-         If you have one optimal path, you should tell Fluke the command seq for the same. If more than one path is optimal, you should tell Fluke all the possible command seq and let him decide

-         Time is of the essence – it is critical that the people be rescued as quickly as possible.

Input

-         The first line contains n where n is the side of the square grid on which the rover will move. 4 <= n <= 100. Top-left co-ordinate is (0,0) and bottom right co-ordinate is (n-1, n-1)

-         The next line is the number of test casesn (2 in the example below) that follow (< 5). Each test case is comprised of a number of lines.

o       The first line of the test case contains the position where the space rover is beamed down/placed initially (facing east).

o       The next line contains the number of survivors, k.

§        This is followed by k lines, each having 3 integers relevant to each survivor. E.g. 1 3 5 indicates that there is a survivor at (1,3) and has Rank 5.

4

2

0 1

4

1 3 5

2 0 5

2 2 1

3 2 3

0 1

5

1 3 5

2 0 5

2 2 5

3 0 5

3 2 3

The test cases represent the following scenarios respectively.

Output

You should print out the results to console (via printf or equivalent)

For each test case, output the maximum cumulative rank of people you can save as the first line. That is to be followed by the command seq (1 or multiple) for the path(s) – See the example below.

8

LB

BL

10

RF

Explanation: