빠른 거북이

파프누티와 친구들은 머릿속으로 복잡한 계산을 빠르게 해야 하는 보드게임을 특히 좋아합니다. 그래서 NUOP(알 수 없는 올림피아드 프로그래밍 대학) 강의실에서는 빠른 거북이 게임이 저녁 모임의 단골 게임이 되었습니다. 게임 구성은 다음과 같습니다.

• 칸으로 나뉜 N행 M열의 격자판. 각 칸은 비어 있거나 이동이 막혀 있습니다.
• Q장의 카드. 각 카드는 시작 칸의 집합 A, 추가로 막히는 칸의 집합 B, 도착 칸의 집합 C를 나타냅니다. A, B, C는 비어 있지 않고 서로 겹치지 않으며, 모두 빈 칸으로만 이루어집니다.
• 거북이 말 하나.

게임 참가자들은 카드를 차례로 뽑습니다. 카드마다 좋은 세 칸 (a_i, b_j, c_k)의 개수를 구해야 합니다. 여기서 a_i는 A의 원소, b_j는 B의 원소, c_k는 C의 원소입니다. 거북이가 칸 b_j를 거치지 않고 시작 칸 a_i에서 도착 칸 c_k까지 이동할 수 있으면 그 세 칸은 좋은 세 칸입니다. 거북이의 이동 조건은 다음과 같습니다.

1. 아래쪽과 오른쪽으로만 움직일 수 있으며, 격자판 안에 머물러야 합니다.
2. 막힌 칸 위에 있을 수 없습니다.
3. 칸 b_j도 이동이 막힌 칸으로 취급합니다.

첫 줄에 정수 N과 M($1 \le N, M \le 150$)이 주어집니다. 이어서 N줄에 걸쳐 위에서 아래, 왼쪽에서 오른쪽 순서로 M글자씩 격자판이 주어집니다. '.'은 빈 칸, '#'은 막힌 칸입니다. 행과 열은 1번부터 번호를 매깁니다.

다음 줄에는 카드의 수 Q($1 \le Q \le 10^5$)가 주어집니다. 각 카드는 세 줄로 된 블록이며, 순서대로 집합 A, B, C를 나타냅니다. 각 줄은 집합의 크기로 시작하고, 그 뒤에 행 번호와 열 번호의 쌍이 이어집니다. 한 설명 안의 칸은 모두 서로 다릅니다.

모든 집합은 비어 있지 않고, 모든 칸은 빈 칸이며, 한 카드 안에서 어떤 칸도 둘 이상의 집합에 속하지 않습니다.

모든 카드의 집합 크기를 합한 값은 $300000$을 넘지 않습니다. 즉 $\sum (|A_i| + |B_i| + |C_i|) \le 300000$입니다. 모든 카드의 세 칸 조합 수 합은 $2 \cdot 10^7$을 넘지 않습니다. 즉 $\sum |A_i| \cdot |B_i| \cdot |C_i| \le 2 \cdot 10^7$입니다.

정확히 Q개의 수를 한 줄에 하나씩 출력합니다. i번째 수는 입력에서 i번째로 주어진 카드의 답입니다.

첫 번째 카드의 모든 세 칸에서 거북이는 왼쪽 위 모서리에서 출발해 오른쪽 아래 모서리에서 끝납니다. 이것이 가능한 경우는 b_j가 2행 1열 칸일 때뿐입니다. 따라서 좋은 세 칸은 $(1,1)$, $(2,1)$, $(5,6)$ 하나입니다.

두 번째 카드의 좋은 세 칸은 $(1,2)$, $(3,1)$, $(5,6)$; $(2,1)$, $(3,1)$, $(5,6)$; $(2,1)$, $(3,1)$, $(5,1)$입니다.