EIUGAME3 - Maximum-sum shortest paths

Given a matrix, find a shortest path from the upper-left cell to the lower-right cell, moving between cells that share an edge. Every shortest path therefore uses only moves right (R) and down (D). Among the shortest paths, find the maximum sum of the values of the visited cells, the number of paths with that sum, and one such path. The sum includes both endpoints. Two paths are different if their sequences of moves differ.

Input

• The first line contains two integers ~n~, ~m~ ~(1 \leq n, m \leq 2000)~.
• Each of the next ~n~ lines contains ~m~ integers ~a_{ij}~ ~(|a_{ij}| \leq 10^9)~.

Output

Print, in order:

1. The maximum sum.
2. The number of maximum-sum shortest paths, modulo ~10^7~.
3. One such path, using R for right and D for down.

Moves may be separated by whitespace or written together. For a ~1 \times 1~ matrix the path is empty, so print only the two integers. Any valid optimal path is accepted. The maximum sum may require a 64-bit integer.

For each test, the maximum sum, count and path are worth 40%, 40% and 20%, respectively, and are checked independently. The first two output tokens are read as the sum and count; all remaining tokens are read as the path. Missing or reordered tokens may be misinterpreted and can result in zero points. If either of the first two tokens is missing, the path cannot be scored.

Example

Input

6 4
12 11 -12 11
12 11 10 12
-11 11 -10 -10
12 -10 -11 10
11 11 11 -10
12 -11 12 12

Output

82
2
D D D D R R D R

Time limit: 2 seconds. Memory limit: 256 MB.

Adapted from EIUGAME2.