Strelice

헨젤과 그레텔이 R행 S열 보드에서 '화살표' 게임을 한다. 보드의 모든 칸에는 상하좌우 네 방향 중 하나를 가리키는 화살표가 정확히 하나씩 그려져 있다.

먼저 헨젤이 마지막 열이 아닌 칸 중 정확히 K개를 색칠한다. 그다음 그레텔이 첫 번째 열의 칸 하나를 골라 로봇을 올려놓는다. 이후 로봇은 스스로 움직이며, 매번 현재 칸의 화살표가 가리키는 칸으로 이동한다. 로봇이 마지막 열의 칸에 도착하면 그 자리에 멈추고 게임이 끝난다.

승자는 다음과 같이 정한다.

• 로봇이 멈춰 게임이 끝났다면, 로봇이 지나간 색칠된 칸이 정확히 하나일 때 헨젤이 이기고 0개이거나 2개 이상일 때 그레텔이 이긴다.
• 로봇이 영원히 멈추지 않으면(무한 루프에 빠지면) 헨젤이 이긴다.

로봇이 지나간 칸에는 출발한 칸, 게임 도중 이동해 온 모든 칸, 게임이 끝났을 때 로봇이 있는 칸이 모두 포함된다. 화살표는 로봇이 보드 밖으로 나가는 일이 없도록 그려져 있다.

그레텔이 로봇을 어디에 놓든 헨젤이 이기도록 색칠할 수 있는지 판단하라. 가능하다면 헨젤이 색칠할 K개의 칸을 출력한다.

첫째 줄에 정수 R, S, K가 주어진다. ($1 \le R \times S \le 1\,000\,000$, $1 \le K \le 50$)

다음 R개의 줄에는 각각 S개의 문자가 주어진다. 각 문자는 'L', 'R', 'U', 'D' 중 하나이며 그 칸에 그려진 화살표의 방향을 나타낸다. L은 왼쪽, R은 오른쪽, U는 위쪽, D는 아래쪽이다.

헨젤이 승리를 보장할 수 없다면 -1을 출력한다.

승리를 보장할 수 있다면 색칠할 K개의 칸을 한 줄에 하나씩 출력한다. 각 줄에는 칸의 행 번호 A와 열 번호 B($1 \le A \le R$, $1 \le B \le S$)를 공백으로 구분해 출력한다. 색칠하는 칸은 모두 서로 달라야 한다. 칸은 행 번호가 작은 순서로, 행 번호가 같으면 열 번호가 작은 순서로 출력한다. 이 순서를 행 우선 순서라고 한다.

헨젤이 이기는 색칠 방법은 여러 가지일 수 있으므로, 다음 규칙으로 정해지는 방법을 출력한다.

• 첫 번째 열의 칸 중 로봇을 놓았을 때 결국 멈추는 칸을 출발 칸이라고 한다.
• 마지막 열이 아닌 칸 중 어떤 출발 칸에서 출발한 로봇이 지나가는 칸을 경로 칸이라 하고, 마지막 열이 아닌 나머지 칸을 여분 칸이라 한다. 여분 칸을 색칠해도 게임 결과는 달라지지 않는다.
• 경로 칸 X에 대해, 거기서 로봇이 출발하면 X를 지나가게 되는 경로 칸 전체(X 포함)를 X의 영역이라 한다. X의 영역에서 정확히 c개의 칸을 색칠해서 X의 영역에 있는 모든 출발 칸에서 출발한 로봇이 색칠한 칸을 정확히 하나 지나가게 할 수 있으면, 양의 정수 c를 X에 가능한 개수라고 한다.
• 경로 칸을 정확히 s개 색칠해서 모든 출발 칸에서 출발한 로봇이 색칠된 칸을 정확히 하나 지나가게 할 수 있고 $K - s$가 여분 칸의 개수 이하인 정수 s($0 \le s \le K$) 중 가장 작은 값을 고른다. 이런 s가 없으면 헨젤은 승리를 보장할 수 없다.
• 여분 칸 중 행 우선 순서로 앞에 있는 $K - s$개를 색칠한다.
• 화살표가 마지막 열의 칸을 가리키는 경로 칸을 최상위 칸이라 한다. 최상위 칸 전체에 s를 아래 방법으로 나눈다.
• 개수 t를 여러 칸에 나눌 때는 칸을 행 우선 순서로 보면서 각 칸에 그 칸에 가능한 개수 중 가장 작은 c를 준다. 단, 남은 개수를 뒤에 오는 칸 각각에 가능한 개수로 남김없이 나눌 수 있어야 한다.
• 개수 c를 받은 칸 X는 이렇게 처리한다. c = 1이면 X를 색칠한다. c ≥ 2이면 X는 색칠하지 않고, 화살표가 X를 가리키는 경로 칸에 c를 같은 방법으로 나눈 뒤 그 칸도 같은 방법으로 처리한다.

첫 번째 예제에서 헨젤이 칸 (1, 2)를 색칠하면 그레텔이 로봇을 어디에 놓든 로봇이 그 칸을 지나가므로 헨젤이 이긴다. 칸 (4, 2)를 색칠해도 헨젤이 이기지만, 출력 규칙에 따른 답은 (1, 2)이다.