화이트보드

거북이 씨는 집에 있는 화이트보드에 그림 그리기를 좋아한다. 어느 날 그림을 그리던 도중에 마커가 말라 버렸다. 그때부터 마커는 지나가는 칸을 칠하지 않고 지우개처럼 지웠다.

거북이 씨는 완성할 그림을 미리 정해 두고, 그리는 과정 전체를 명령 목록으로 계획한다. 명령 하나는 방향(up, down, left, right)과 이동 거리로 이루어진다. 출발 칸은 화이트보드의 왼쪽 아래 칸이다.

시간은 타임스텝으로 센다. 타임스텝 0은 마커가 아직 보드에 닿지 않은 순간이다. 타임스텝 1에 마커는 출발 칸 위에 있고, 한 칸 움직일 때마다 타임스텝이 1씩 늘어난다. 명령의 이동 거리를 모두 더한 값을 $d$라고 하면, 마커가 보드 위에 있는 마지막 타임스텝은 $1 + d$이다.

마커가 타임스텝 $T$에 말랐다고 하자. $1 \le t \le T$인 타임스텝 $t$마다 마커는 그 순간 놓인 칸을 칠하고, $t > T$인 타임스텝마다 그 칸을 지운다. 지워진 칸은 앞서 무엇이 칠해져 있었든 빈 칸이 된다. 타임스텝 17에 마른 마커는 타임스텝 17에는 칠하지만 타임스텝 18에는 지운다. $T = 0$도 가능하며, 이때 보드는 끝까지 비어 있다.

화이트보드의 크기, 목표 그림, 명령 목록이 주어진다. 최종 보드가 목표 그림과 같아지는 $T$의 최솟값과 최댓값을 구하라.

아래 그림은 $6 \times 8$ 화이트보드와 명령 다섯 개로 이루어진 계획, 그리고 마커가 타임스텝 17에 말랐을 때 남는 보드를 보여 준다. 칸에 적힌 수는 마커가 그 칸에 놓이는 타임스텝이다.

첫 줄에 세 정수 $h$, $w$, $n$이 주어진다 ($1 \le h, w, n \le 1\,000\,000$, $h \cdot w \le 1\,000\,000$). $h$와 $w$는 화이트보드의 높이와 너비이고, $n$은 명령의 개수이다.

다음 $h$개 줄에는 각각 정확히 $w$개의 문자가 주어지며, 목표 그림을 맨 윗줄부터 맨 아랫줄까지 나타낸다. #는 칠해진 칸, .는 빈 칸이다.

다음 $n$개 줄에는 각각 명령이 방향 거리 형식으로 주어진다. 두 부분은 공백 하나로 구분하고, 줄에 다른 공백은 없다. 방향은 up, down, left, right 중 하나이며 모두 소문자이다. 거리는 $1$ 이상 $1\,000\,000$ 이하의 정수이다. 명령은 주어진 순서대로 수행한다. 어떤 명령도 마커를 화이트보드 밖으로 내보내지 않는다.

한 줄에 정수 두 개를 출력한다. 최종 보드가 목표 그림과 같아지도록 마커가 마를 수 있는 타임스텝의 최솟값을 먼저, 최댓값을 그다음에 출력한다. 두 값 모두 마커가 보드 위에 있는 마지막 타임스텝을 넘을 수 없다. 마커가 끝까지 마르지 않아도 목표 그림이 나온다면 최댓값으로 그 마지막 타임스텝을 출력한다. 목표 그림을 만들 수 없으면 -1 -1을 출력한다.