젤리 습격

아데파기아 기숙학교 학생들은 저녁 식사 뒤가 초라하다. 예산을 줄이면서 후식이 비스킷 한 조각으로 깎였는데, 선생들은 매일 저녁을 라즈베리 젤리로 마무리한다. 커스터드 크림이나 부르봉도 나쁜 비스킷은 아니지만 아이들이 원하는 것은 젤리다. 그래서 한밤중 습격을 계획했다.

아이 한 명이 기숙사 침대에서 출발해 학교를 가로질러 주방 냉장고까지, 순찰하는 선생에게 들키지 않고 가야 한다.

학교는 $r$ 행 $c$ 열 격자이고, 각 칸은 지나갈 수 있는 칸이거나 막힌 칸이다. 시간은 $0$ 번 턴부터 흐른다. $0$ 번 턴에 아이는 침대 위에 있고, 각 선생은 자기 순찰 경로의 첫 좌표에 있다.

그다음 매 턴마다 아이는 제자리에 머무르거나, 지금 칸과 변을 맞댄 지나갈 수 있는 칸으로 한 칸 움직인다. 같은 턴에 모든 선생이 자기 경로를 따라 한 걸음 나아간다. 선생은 경로의 첫 좌표에서 마지막 좌표까지 걸어간 뒤 방향을 돌려 첫 좌표로 돌아오고, 이 왕복을 끝없이 되풀이한다. 좌표가 하나뿐인 경로를 맡은 선생은 움직이지 않는다.

선생은 자기가 선 행과 열을 따라 본다. 어떤 턴이 끝난 시점에 아이와 어떤 선생이 같은 행이나 같은 열에 있고 그 사이의 칸이 모두 지나갈 수 있는 칸이면 아이는 들킨다. 선생이 아이와 같은 칸에 서 있어도 들킨다. 선생은 다른 선생의 시야를 막지 않고, 시야를 막는 것은 막힌 칸뿐이다. 이 판정은 $0$ 번 턴에도 똑같이 적용된다.

아이가 냉장고 칸에 서는 순간 습격은 끝난다. 그 턴에 들키는 것은 상관없다. 아이는 들키지 않고 침대로 돌아가거나, 젤리를 배불리 먹고 붙잡히더라도 개의치 않기 때문이다. 첫 번째 예제가 그런 경우다. 아이는 26번째 턴에 냉장고에 닿고, 바로 그 턴에 선생에게 들킨다.

첫째 줄에 정수 $r$ 와 $c$ 가 주어진다 ( $1 < r, c \le 60$ ). 각각 학교의 행 수와 열 수다.

둘째 줄에 좌표 두 개가 주어진다. 앞은 기숙사 침대, 뒤는 주방 냉장고의 위치다. 좌표는 행 번호와 열 번호를 괄호 안에 적는다. 예를 들어 (2 5)이다.

다음 $r$ 개 줄에는 각각 문자 $c$ 개가 주어진다.

. 지나갈 수 있는 칸
# 막힌 칸

다음 줄에 순찰하는 선생의 수 $p$ 가 주어진다 ( $1 \le p \le 200$ ).

다음 $p$ 개 줄에는 각각 순찰 경로 하나가 주어진다. 정수 $k$ ( $1 \le k \le 7$ ) 뒤에 좌표 $k$ 개가 온다. 한 경로에서 이웃한 두 좌표는 서로 같거나 변을 맞대고 있다.

침대, 냉장고, 모든 경로 좌표는 지나갈 수 있는 칸이다.

문제

입력

출력