Volcano

Time Limit: 1 Second    Memory Limit: 32768 KB

Now suppose that you are an important man who must execute an important mission. The first thing you must do is to walk through a volcano zone.

We assume that the volcano zone is a n*m matrix, and your original position is at top left corner of the matrix (1, 1). Each volcano takes one grid, and will bursts out at some time and ends up within a unit of time. Also it will burst out again after a period of time. There will not be any volcano in the first row (row 1) and last row (row n) of the matrix. Your task is to walk from the original position to the last row (any grid) safely to get away. Note that every step you walk will takes one unit of time and you can also linger in some grid.

Now your task is to work out the paths that you can safely get to the last row of the matrix using minimal steps.

Input

The input consists of several test cases.

The first line of each test case contains three integer n, m, k. (2 <= n <= 15, 1 <= m <= 15) (The size of the matrix is n * m, and the k is the number of the volcanoes.) Then each of the following k lines contains four integers t0, T, x, y. (t0 is the first time this volcano bursts out, T (1 <= T <= 6) is the period between two bursts (T = 1 means that the volcano will bursts all the time), and (x, y) is the position of this volcano).

Note that the mission will begin at time 0.

The input is ended by EOF.

Output

For each case, first output the number of the test case (`Case 1:', ` Case 2:', etc.) in a line of its own.

If it is possible to get to the last row, print a line containing the path which you walk through using minimal steps. Each step you will print a letter among F, B, L, R and S, F and B denotes walk forward or backward, L and R denotes go to the left or right grid , and S denotes to linger in that grid.

Note that your original direction orients to the last row.

If there are more than one path, choose the lexicographical smallest one.

If you can't get to the last row, output a line containing the statement `No'.

Output a blank line after each test case.

Sample Input

4 4 7 
1 1 2 2 
1 1 2 3 
1 1 2 4 
2 4 3 1 
3 4 3 2 
0 4 3 3 
1 4 3 4 
5 4 10 
1 1 2 2 
1 1 2 3 
1 1 2 4 
2 4 3 1 
3 4 3 2 
0 4 3 3 
1 4 3 4 
1 1 4 1 
1 1 4 2 
1 1 4 3

Sample Output

Case 1:
FSFF

Case 2:
FSFLFFRF

Submit

Source: ZOJ Monthly, March 2004