Collecting Apples

Santi is playing a game on a grid with $R$ rows (from top to bottom) and $C$ columns (from left to right). The cell in the $i$th row and $j$th column is called cell $(i, j)$. Cell $(i, j)$ contains $A_{i,j}$ apples.

Santi's character Nano starts on cell $(1, 1)$ and wants to move to cell $(R, C)$. On each turn Nano can move only one cell down or one cell right, which brings it closer to the goal. Nano's path to the goal can be written as a string of $R + C - 2$ characters, of which $R - 1$ are ‘D’ and $C - 1$ are ‘R’. This means that Nano moves one cell down on the $i$th turn if the $i$th character is ‘D’, and one cell right on the $i$th turn if the $i$th character is ‘R’.

Two paths are different if their string representations are different. There are $R+C-2 \choose R-1$ different paths. Path $X$ is better than path $Y$ if either of the following holds:

• Path $X$ collects more apples than $Y$. The number of apples Nano collects along a path is the total number of apples in the cells the path passes through, including cell $(1, 1)$ and cell $(R, C)$.
• Path $X$ collects the same number of apples as $Y$, and the string representation of $X$ is lexicographically smaller than the string representation of $Y$.

Finding the best path is too boring for Santi, so she wants to find the $K$th best path instead. In other words, she wants to find a path $X$ such that $K - 1$ paths are better than $X$ and ${R+C-2 \choose R-1} - K$ paths are worse than $X$.

For example, let $R = 2$, $C = 3$, $K = 3$, $A_{1,1..3} = \{1, 2, 3\}$, and $A_{2,1..3} = \{2, 2, 3\}$. Then there are three different paths to the goal, listed from best to worst.

1. The path represented by the string RRD. It collects $1 + 2 + 3 + 3 = 9$ apples.
2. The path represented by the string DRR. It collects $1 + 2 + 2 + 3 = 8$ apples.
3. The path represented by the string RDR. It collects $1 + 2 + 2 + 3 = 8$ apples.

Therefore, the $3$rd best path is the path represented by the string RDR.

The first line contains three integers $R$ $C$ $K$ ($2 \le R, C \le 30; 1 \le K \le {R+C-2 \choose R-1}$), which are the number of rows, the number of columns, and the index of the path Santi wants to find. The next $R$ lines each contain $C$ integers giving the number of apples in each cell. The $j$th integer on the $i$th line is $A_{i,j}$ ($0 \le A_{i,j} \le 200$).

Print one line containing the string that represents the $K$th best path to the goal.