G. Matrix Cycle
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a matrix of size $$$n \times m$$$, consisting of positive integers.

You can choose any starting cell of the matrix. In one move, you can either move down or to the right in the matrix. A move from cell $$$(n, j)$$$ down moves you to cell $$$(1, j)$$$, and a move from cell $$$(i, m)$$$ to the right moves you to cell $$$(i, 1)$$$. Your task is to make exactly $$$n$$$ moves down and exactly $$$m$$$ moves to the right, returning to the original cell in such a way that no cell in the matrix is visited twice (except for the starting cell).

Find a way to choose the starting cell and make $$$n+m$$$ moves as described above, such that the sum of the numbers in the visited cells is maximal.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 1\,500$$$) — the dimensions of the matrix.

The next $$$n$$$ lines contain $$$m$$$ positive integers each, where the $$$i$$$-th of these lines contains the numbers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ ($$$1 \le a_{i, j} \le 1\,000\,000$$$).

Output

In the first line, print the maximum sum that can be obtained with $$$n+m$$$ moves.

In the second line, print two numbers $$$r$$$ and $$$c$$$ — the row and column number of the starting cell in the optimal way.

In the last line, print a string of $$$n+m$$$ characters consisting of exactly $$$n$$$ characters 'D' and exactly $$$m$$$ characters 'R', corresponding to the optimal sequence of moves. The character 'D' corresponds to a move down, and the character 'R' corresponds to a move to the right.

Examples
Input
2 2
1 2
3 4
Output
10
1 1
DRDR
Input
3 3
1 2 3
4 5 6
7 8 9
Output
37
1 2
DRDRRD
Input
3 3
9 1 1
9 9 9
9 1 1
Output
46
1 1
DRRDRD
Input
3 7
74 68 24 42 27 1 81
57 67 49 40 1 92 83
34 88 86 45 32 48 24
Output
613
1 2
DDRRRRRDRR