물고기

먼 바다의 군도에 희귀한 육식성 물고기가 산다. 이 물고기의 하루는 아주 규칙적이다. 아침마다 같은 시각에 깨어나 사냥을 나가고, 저녁이면 출발한 자리로 돌아와 역시 매일 같은 시각에 잠든다. 잠든 사이 해류에 조금 떠밀리기 때문에 다음 날 아침에는 다른 자리에서 깨어나기도 한다.

하루 동안 물고기는 한 가지 규칙을 지킨다. 매 순간, 정확히 24시간 전인 전날 같은 시각에 자기가 있던 지점이 보여야 한다. 섬 반대편에 있는 지점은 볼 수 없다.

어류학자들은 오랫동안 이 군도를 관찰하면서 며칠에 한 번씩 물고기 한 마리의 경로를 기록했다. 자료가 많이 쌓였을 무렵 사고가 나서 일부는 사라지고 남은 기록은 뒤섞였다. 어떤 경로를 어떤 물고기가 헤엄쳤는지조차 알 수 없다. 남은 경로 기록과 모순되지 않는 물고기 수의 최솟값을 구하라.

첫 줄에 정수 $w$와 $h$가 공백 하나를 사이에 두고 주어진다 ($3 \le w \le 1000$, $3 \le h \le 1000$). 다음 $h$개 줄에는 군도의 한 행을 나타내는 길이 $w$의 문자열이 하나씩 주어진다. 문자 .은 바다, #은 육지다. 지도 테두리에 있는 칸은 모두 바다다.

군도의 한 지점에서 다른 지점이 보인다는 것은, 두 지점을 잇는 선분이 어떤 육지의 내부나 경계와도 만나지 않는다는 뜻이다. 물고기가 어느 방향으로 헤엄치는지는 여기서 상관없다.

그다음 줄에는 기록된 경로의 수 $n$이 주어진다 ($2 \le n \le 1000$). 이어지는 $2n$개 줄이 경로를 설명한다. 각 설명의 첫 줄에는 정수 $x$, $y$, $d$가 공백 하나씩을 사이에 두고 주어진다 ($1 \le x \le w$, $1 \le y \le h$, $2 \le d \le 10000$). $x$와 $y$는 물고기가 깨어난 칸의 열과 행이고, $d$는 경로의 길이다. 둘째 줄에는 N, W, S, E 네 문자로 이루어진 길이 $d$의 문자열이 주어지며, 각 문자는 차례로 위, 왼쪽, 아래, 오른쪽으로 한 칸 움직이는 것을 뜻한다. 모든 경로는 바다 칸만 지나고, 입력으로 주어진 군도 조각을 벗어나지 않으며, 출발한 칸에서 끝난다.

물고기는 가로나 세로로만 움직이며, 지나는 칸의 중심을 이은 꺾은선을 따라 헤엄친다. 속도는 알 수 없다. 정확히 24시간 전에 있던 지점을 항상 볼 수 있도록 빨라지거나 느려질 수 있다.

해류는 잠든 물고기를 잠든 칸에서 위, 아래, 왼쪽, 오른쪽으로 최대 한 칸 옮긴다. 군도의 바다 칸 두 개를 어떻게 고르더라도 두 칸을 모두 지나는 (가상의) 물고기 경로가 존재한다고 가정해도 된다.

첫 줄에 기록과 모순되지 않는 물고기 수의 최솟값 $k$를 출력한다. 이어지는 $k$개 줄에는 물고기 한 마리가 헤엄친 경로의 번호를 쓴다. 한 물고기가 그 경로를 연이은 날에 헤엄쳤을 필요는 없고, 사는 동안의 어느 이틀이어도 된다.

한 물고기가 이틀 연속으로 두 경로를 헤엄칠 수 있으려면, 두 경로의 출발 칸이 같거나 변을 맞대고 있어야 하고, 정확히 24시간 전에 있던 지점을 매 순간 보면서 둘째 경로를 헤엄칠 수 있어야 한다.

경로에는 입력에 나온 순서대로 1번부터 $n$번까지 번호를 매긴다. 한 줄 안의 번호는 증가하는 순서로 쓰고, 각 줄의 첫 번호가 증가하도록 줄을 정렬한다. $k$와 이 묶음은 유일하게 정해진다.

예제에서 처음 두 경로는 한 물고기가 이틀 연속으로 헤엄쳤을 수도 있다. 며칠 뒤 같은 물고기가 세 번째 경로를 헤엄쳤을 수도 있다. 네 번째 경로는 다른 물고기의 것이다. 앞의 세 경로와 달리 큰 섬을 크게 돌아 나가기 때문이다.