사과 수집

Santi는 $R$개의 행(위에서 아래로)과 $C$개의 열(왼쪽에서 오른쪽으로)로 이루어진 격자에서 게임을 한다. $i$번째 행과 $j$번째 열의 칸을 $(i, j)$라고 하자. $(i, j)$ 칸에는 $A_{i,j}$개의 사과가 있다.

Santi의 캐릭터 Nano는 처음에 $(1, 1)$ 칸에 있으며 $(R, C)$ 칸으로 이동하려고 한다. Nano는 매 턴마다 아래로 한 칸 또는 오른쪽으로 한 칸만 이동할 수 있고, 그렇게 해서 목표에 가까워진다. 목표까지 가는 Nano의 경로는 $R + C - 2$개의 문자로 이루어진 문자열로 나타낼 수 있으며, 그중 $R - 1$개는 ‘D’이고 $C - 1$개는 ‘R’이다. $i$번째 문자가 ‘D’이면 Nano는 $i$번째 턴에 아래로 한 칸 이동하고, $i$번째 문자가 ‘R’이면 오른쪽으로 한 칸 이동한다는 뜻이다.

두 경로는 문자열 표현이 다르면 서로 다른 경로이다. 서로 다른 경로는 $R+C-2 \choose R-1$개 있다. 경로 $X$가 경로 $Y$보다 좋다는 것은 다음 중 하나가 성립한다는 뜻이다.

• 경로 $X$가 $Y$보다 사과를 많이 모은다. Nano가 경로에서 모으는 사과의 수는 $(1, 1)$ 칸과 $(R, C)$ 칸을 포함하여 경로가 지나는 칸에 있는 사과의 총합이다.
• 경로 $X$가 $Y$와 사과를 같은 개수만큼 모으고, $X$의 문자열 표현이 $Y$의 문자열 표현보다 사전순으로 앞선다.

가장 좋은 경로를 찾는 것은 Santi에게 너무 지루하기 때문에, 대신 $K$번째로 좋은 경로를 찾으려고 한다. 다시 말해, $X$보다 좋은 경로가 $K - 1$개 있고 $X$보다 나쁜 경로가 ${R+C-2 \choose R-1} - K$개인 경로 $X$를 찾으려고 한다.

예를 들어 $R = 2$, $C = 3$, $K = 3$, $A_{1,1..3} = \{1, 2, 3\}$, $A_{2,1..3} = \{2, 2, 3\}$이라고 하자. 그러면 목표까지 가는 서로 다른 경로가 세 개 있고, 좋은 순서대로 나열하면 다음과 같다.

1. 문자열 RRD로 나타내는 경로. 이 경로는 사과를 $1 + 2 + 3 + 3 = 9$개 모은다.
2. 문자열 DRR로 나타내는 경로. 이 경로는 사과를 $1 + 2 + 2 + 3 = 8$개 모은다.
3. 문자열 RDR로 나타내는 경로. 이 경로는 사과를 $1 + 2 + 2 + 3 = 8$개 모은다.

따라서 $3$번째로 좋은 경로는 문자열 RDR로 나타내는 경로이다.

첫 줄에 세 정수 $R$ $C$ $K$가 주어진다. ($2 \le R, C \le 30; 1 \le K \le {R+C-2 \choose R-1}$) 각각 행의 수, 열의 수, Santi가 찾으려는 경로의 순번이다. 다음 $R$개의 줄에 각각 $C$개의 정수가 주어지며, 각 칸에 있는 사과의 수를 나타낸다. $i$번째 줄의 $j$번째 정수는 $A_{i,j}$이다. ($0 \le A_{i,j} \le 200$)

목표까지 가는 $K$번째로 좋은 경로를 나타내는 문자열을 한 줄에 출력한다.