TV Game

In a well-known TV game, a player stands in front of a vertical rectangular board with $N$ rows and $M$ columns. The player picks one of the columns and drops a ball into it. The ball falls down through the cells one after another until it reaches the bottom of the board. On its way down, the ball can move from one column to another, depending on the symbol in each cell it enters.

• '.': the ball keeps falling straight down. If the ball is in row $i$, column $j$, and the cell holds '.', it moves to row $i+1$, column $j$.
• 'L': the ball falls to the lower left. If the ball is in row $i$, column $j$, and the cell holds 'L', it moves to row $i+1$, column $j-1$.
• 'R': the ball falls to the lower right. If the ball is in row $i$, column $j$, and the cell holds 'R', it moves to row $i+1$, column $j+1$.
• 'X': the ball stops in this cell, and the player decides where it goes next. There are three choices: the lower left cell, the cell directly below, or the lower right cell.
• A digit from 0 to 9: the player adds the digit's value, in thousands of leva, to their winnings. The ball then falls to the cell below, if there is one.

Write a program tvgame that finds the largest total the player can collect and shows one way to reach it.

The first line contains two integers $N$, the number of rows, and $M$, the number of columns. The next $N$ lines each contain $M$ characters that describe the board.

On the first line, print the largest total the player can collect, in thousands of leva.

On the second line, print the number of the column where the ball must be dropped to reach that total.

On the third line, print the path of the ball. For each move from one cell to the next, print one character: L if the ball moves to the lower left cell, D if it moves to the cell directly below, or R if it moves to the lower right cell.

$0 < N, M < 1000$

Rows and columns are numbered starting from 1. When the ball is dropped into column $j$, it first lands in row 1, column $j$.

All cells in the first column, the last column, and the bottom row contain digits.