import java.io.*;

class BDDP
{
    static int[] [] bestCount;
    static boolean[] bestStep;

    public static void main (String[] args) throws IOException
    {
	BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
	String input = "";
	while (!input.equals ("quit"))
	{
	    long t1 = System.currentTimeMillis ();
	    System.out.println ("----\n");
	    int[] [] cell = new int [randint (4, 4)] [randint (4, 4)];
	    bestCount = new int [cell.length] [cell [0].length];
	    for (int i = 0 ; i < cell.length ; i++)
	    {
		for (int j = 0 ; j < cell [i].length ; j++)
		{
		    cell [i] [j] = randint (0, 9);
		    System.out.print (cell [i] [j] + " ");
		    bestCount [i] [j] = -1;
		}
		System.out.println ();
	    }

	    boolean[] step = new boolean [cell.length + cell [0].length - 2];
	    recursion (cell, step, 0, 0, 0);
	    System.out.println ("\nIn this " + cell.length + "x" + cell [0].length + " array,");
	    for (int i = 0 ; i < bestStep.length ; i++)
		System.out.print (bestStep [i] ? 'R':
		'D');
	    System.out.println (" gives the maximum of " + bestCount [bestCount.length - 1] [bestCount [0].length - 1] + " apples.");
	    System.out.println ("Time: " + (System.currentTimeMillis () - t1) + " ms");
	    System.out.println ("\nEnter anything except \"quit\" to restart");
	    input = br.readLine ().trim ().toLowerCase ();
	}
    }


    static void recursion (int[] [] cell, boolean[] step, int i, int j, int count)
    {
	try
	{
	    count += cell [i] [j];
	    if (count > bestCount [i] [j])
	    {
		bestCount [i] [j] = count;
		int curStep = i + j;
		if (curStep == step.length)
		{
		    bestStep = step;
		    return;
		}
		// Go right
		step [curStep] = true;
		recursion (cell, (boolean[]) (step.clone ()), i, j + 1, count);
		// Go down
		step [curStep] = false;
		recursion (cell, (boolean[]) (step.clone ()), i + 1, j, count);
	    }
	}
	catch (ArrayIndexOutOfBoundsException aiooe)
	{
	}
    }


    static int randint (int a, int b)
    {
	return Math.min (a, b) + (int) (Math.random () * (Math.abs (b - a) + 1));
    }
}