파댕이의 학교 탈출 대작전!

고등학생이 된 파댕이는 떡볶이와 튀김이 먹고 싶어졌다. 그래서 점심시간에 학교를 몰래 빠져나가 분식점에 가기로 계획했다.

학교를 나가려고 주변을 살펴보니 선생님들이 주변을 감시하고 있어 쉽게 출입할 수 없었다. 파댕이가 선생님의 감시에 걸리지 않고 점심시간 안에 떡볶이를 먹고 교실로 돌아올 수 있는지 확인해 보자.

학교는 $N \times M$ 크기의 격자 구조이다. 파댕이에 대해 다음 사실을 알아냈다.

• 탈출을 결심한 시점은 $t = 1$이며, 교실로 돌아왔을 때에도 $t \le T$를 만족해야 한다.
• 파댕이는 교실에 있으며, 교실은 $(1, 1)$ 칸에, 분식점은 $(N, M)$ 칸에 있다.
• 각 칸에서 #은 장애물, .은 빈 공간을 뜻한다. 선생님과 파댕이는 장애물 위를 지나갈 수 없고, 지도 밖으로도 나갈 수 없다.
• $t \equiv 5 \pmod{10}$일 때마다 파댕이는 가만히 있거나 인접한 칸으로 이동할 수 있다. 식사를 끝낸 시점 $t_{eat}$이 $t_{eat} \equiv 5 \pmod{10}$이면, 식사를 끝내자마자 바로 이동할 수 있다.
• 선생님은 주어진 경로를 순서대로 따라 이동하며, $t \equiv 0 \pmod{10}$일 때 이동한다.
• 선생님은 인접한 8칸을 감시한다. 한 칸 위에 선생님이 여러 명 있을 수도 있다. 파댕이는 모든 시점에 선생님의 감시에 걸리면 안 된다. 단, 인접한 칸으로 이동하는 도중에는 감시에 걸리지 않는다.
• 파댕이가 교실이나 분식점에 있을 때는 감시에 걸리지 않는다.

두 칸 $(a, b)$와 $(x, y)$가 인접한다는 것은 $\max(|a - x|, |b - y|) = 1$임을 뜻한다.

첫째 줄에 지도의 세로 길이 $N$, 가로 길이 $M$, 선생님의 수 $L$, 남은 점심시간 $T$, 떡볶이와 튀김을 먹는 데 걸리는 시간 $K$가 정수로 주어진다. $(2 \le N, M \le 1,000; 1 \le L \le 2,000; 1 \le T \le 3,600; 1 \le K \le T)$ 둘째 줄부터 $N$개의 줄에 지도가 주어진다. 왼쪽 위 꼭짓점의 좌표는 $(1, 1)$, 오른쪽 아래 꼭짓점의 좌표는 $(N, M)$이며, $(1, 1)$ 칸과 $(N, M)$ 칸에는 장애물이 없다. 다음 줄부터 $L$명의 선생님 정보가 주어진다. 각 선생님의 첫째 줄에는 이동 경로 길이 $p$가 주어진다. $(1 \le p \le 100)$ 이어서 $p$개의 줄에 이동 경로 $x_i, y_i$가 주어진다. $(1 \le x_i \le N; 1 \le y_i \le M)$

파댕이가 떡볶이와 튀김을 사 먹고 교실로 돌아올 수 있다면 YUMMY, 없다면 SAD를 출력한다.

$t = n$일 때 선생님의 위치는 $(x_{(\lfloor \frac{n}{10} \rfloor \bmod p + 1)}, y_{(\lfloor \frac{n}{10} \rfloor \bmod p + 1)})$이다.