Chip Play

다음 게임을 생각해 보자. 크기가 n × m인 직사각형 필드가 있다. 필드의 일부 칸에는 칩이 놓여 있다.

각 칩에는 화살표가 그려져 있다. 따라서 필드의 각 칩은 위, 아래, 왼쪽, 오른쪽 중 한 방향을 가리킨다.

플레이어는 칩 하나를 선택하여 그 칩으로 한 번의 이동을 할 수 있다.

이동은 다음과 같은 일련의 동작으로 이루어진다. 선택한 칩을 현재 칩으로 표시한다. 그다음 플레이어는 현재 칩의 화살표가 가리키는 방향으로, 현재 칩과 같은 행 또는 같은 열에 다른 칩이 더 있는지 확인한다. 칩이 적어도 하나 있다면 그중 가장 가까운 칩을 새로운 현재 칩으로 표시하고, 이전 현재 칩을 필드에서 제거한다. 그 후 이 확인을 반복한다. 이 과정은 여러 번 반복될 수 있다. 새로운 칩을 찾지 못하면 현재 칩을 필드에서 제거하고 플레이어의 이동이 끝난다.

이동이 끝나면 플레이어는 제거된 칩의 수와 같은 점수를 얻는다.

주어진 초기 칩 배치에서 플레이어가 한 번의 이동으로 얻을 수 있는 최대 점수를 구한다. 또한 그러한 이동의 수도 구한다.

첫째 줄에는 두 정수 n와 m가 주어진다 (1 ≤ n, m, n × m ≤ 5000). 이어서 각각 m개의 문자를 포함하는 n개의 줄이 주어지며, 이는 게임 필드의 설명이다. "."는 해당 칸이 비어 있음을 의미한다. "L", "R", "U", "D"는 해당 칸에 칩이 있으며 그 칩의 화살표가 각각 왼쪽, 오른쪽, 위쪽, 아래쪽을 가리킨다는 의미이다.

필드에 적어도 하나의 칩이 있다는 것이 보장된다.

두 수, 즉 플레이어가 한 번의 이동 후 얻을 수 있는 최대 점수와 이 최대 점수를 얻을 수 있는 이동의 수를 출력한다.

첫 번째 예제에서는 위치 (3, 3)의 칩으로 최대 점수를 얻는다. 다음 그림에서 그 진행 과정을 볼 수 있다.

다른 모든 칩은 더 적은 점수를 얻는다.