로봇 청소기

$N \times M$ 크기의 격자 모양 마루가 있다. 위에서부터 $r$ 번째 행, 왼쪽에서부터 $c$ 번째 열에 있는 마루의 칸은 $(r, c)$로 나타낸다. 마루는 자주 더러워지기 때문에 평소 관리를 위해 로봇 청소기를 사용하고 있다.

로봇 청소기가 청소를 시작하면 첫 행의 임의의 칸에서 출발하여, 이동하면서 지나가는 칸을 모두 청소한다. 그렇게 첫 행에서 출발하여 마지막 행에 도착하면 한 번의 청소를 끝낸 것이다.

로봇 청소기가 격자 위를 이동하는 방법은 L, D, R의 세 가지인데, 로봇 청소기의 현재 위치가 $(r, c)$라면

• L은 $(r+1, c-1)$로 이동하는 것이다. 단, 해당하는 칸이 존재해야 한다.
• D는 $(r+1, c)$로 이동하는 것이다.
• R은 $(r+1, c+1)$로 이동하는 것이다. 단, 해당하는 칸이 존재해야 한다.

각 방법에 따른 로봇 청소기의 이동 위치를 그림으로 나타내면 다음과 같다.

지금 반드시 청소가 필요한 칸에 X 표시가 되어있어서, 로봇 청소기는 청소해야 하는 칸들을 모두 한 번 이상 청소할 때까지 청소를 반복한다.

아래 그림은 $4 \times 5$ 크기의 격자 모양 마루에서 로봇 청소기가 어떻게 청소하는지에 대한 예시를 보여준다. 이 경우, X 표시가 된 곳을 모두 청소하기 위해서는 로봇이 두 번 청소해야 함을 알 수 있다.

격자에 대한 정보가 주어진다. 로봇 청소기가 청소해야 하는 최소 횟수를 구하고, 실제로 어떤 과정을 거쳐 청소해야 하는지 구하는 프로그램을 작성하시오.

입력 형식

첫 줄에 격자의 크기를 나타내는 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. ($2 \le N, M;$ $N \times M \le 1\,000\,000$)

이어지는 $N$ 줄의 각 줄에 길이가 $M$ 인 문자열이 주어지는데, 이 문자열은 O와 X로만 구성되어 있고, X는 그 칸이 청소가 필요한 칸임을 나타낸다.

출력 형식

첫 줄에 로봇이 청소해야 하는 최소 횟수 $K$를 출력한다.

이어지는 $K$ 줄의 각 줄에는 실제로 청소하는 과정을 출력한다. 한 번의 과정은 로봇이 첫 행에서 이동을 시작한 열의 번호 $c$ ($1 \le c \le M$)와 L, D, R로 구성된 길이 $N-1$인 문자열로 이동 방법을 순서대로 나타내야 한다.

만약 답이 여러 가지인 경우, 그중 아무거나 하나 출력한다.

예제 1

4 5
OOOXO
OXOOO
OXOOO
OOXOO

2
4 LLD
2 DRD

예제 2

4 4
XOOX
OXXO
OXXO
XOOX

2
1 RRR
4 LLL

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

청소 과정이 올바르지 않아도 최소 횟수가 맞는다면 50%의 부분점수를 받는다. 단, 이를 위해서는 청소 과정을 하나도 출력하지 않거나, 출력 형식을 완벽히 지켜서 출력해야 한다.

해설