Padaengi's Great Escape from School!

Padaengi is in high school and craves tteokbokki and fried food. So during lunch break, Padaengi plans to sneak out of school and go to the snack bar.

Padaengi looks around and sees teachers watching the area, so leaving is not easy. Check whether Padaengi can eat tteokbokki and return to the classroom within the lunch break without being spotted by a teacher.

The school is an $N \times M$ grid. Padaengi knows the following.

• Padaengi decides to escape at $t = 1$, and must satisfy $t \le T$ when returning to the classroom.
• Padaengi is in the classroom at cell $(1, 1)$, and the snack bar is at cell $(N, M)$.
• In each cell, # is an obstacle and . is empty. Teachers and Padaengi cannot pass through obstacles or leave the map.
• At every $t \equiv 5 \pmod{10}$, Padaengi can stay still or move to an adjacent cell. If the time $t_{eat}$ when Padaengi finishes eating satisfies $t_{eat} \equiv 5 \pmod{10}$, Padaengi can move right after finishing.
• Teachers follow their given routes in order and move when $t \equiv 0 \pmod{10}$.
• A teacher watches the 8 adjacent cells. Several teachers can stand on the same cell. Padaengi must not be watched by a teacher at any time. Padaengi is safe while moving between adjacent cells.
• Padaengi is not watched while in the classroom or at the snack bar.

Two cells $(a, b)$ and $(x, y)$ are adjacent when $\max(|a - x|, |b - y|) = 1$.

The first line contains the grid height $N$, width $M$, the number of teachers $L$, the remaining lunch time $T$, and the time $K$ needed to eat tteokbokki and fried food, all as integers. $(2 \le N, M \le 1,000; 1 \le L \le 2,000; 1 \le T \le 3,600; 1 \le K \le T)$ The next $N$ lines give the map. The top left corner is $(1, 1)$ and the bottom right corner is $(N, M)$. Cells $(1, 1)$ and $(N, M)$ have no obstacles. The next data describes $L$ teachers. Each teacher's first line gives the route length $p$. $(1 \le p \le 100)$ The next $p$ lines give the route $x_i, y_i$. $(1 \le x_i \le N; 1 \le y_i \le M)$

Print YUMMY if Padaengi can eat tteokbokki and fried food and return to the classroom. Otherwise, print SAD.

The position of the teacher at $t = n$ is $(x_{(\lfloor \frac{n}{10} \rfloor \bmod p + 1)}, y_{(\lfloor \frac{n}{10} \rfloor \bmod p + 1)})$.