환각을 일으키는 카네이션

어떤 농부가 아주 오래전부터 환각을 일으키는 카네이션을 재배해 왔다. 카네이션은 같은 크기의 정사각형 구획으로 나뉜 직사각형 밭에서 자란다. 각 구획에는 일정한 수의 카네이션이 자라며, 신기하게도 오랜 세월 동안 같은 구획에서는 언제나 같은 수의 카네이션이 자란다.

매년 여름 첫날, 농부는 수확을 시작한다. 농부는 밭 위에 다각형을 하나 그리는데, 이 다각형의 모든 꼭짓점 좌표는 정수이고, 각 변은 밭의 변에 대해 평행하거나 수직이거나 또는 $45$, $135$, $225$, $315$도로 비스듬하다. 이 다각형은 단순 다각형이다. 즉, 두 변이 한 점에서 만나는 경우는 오직 그 두 변이 이웃한 변일 때뿐이다.

농부는 이렇게 그린 다각형을 이용해, 어떤 구획의 넓이 중 절반 이상이 다각형 내부에 들어가는 경우 그 구획의 카네이션을 모두 수확한다. 수확되지 않은 카네이션은 이런저런 생물들이 먹어 치운다.

해마다 농부가 수확한 카네이션은 각각 몇 송이인가?

첫째 줄에 테스트의 수 $d$ ($1 \le d \le 10$)가 주어진다.

각 테스트의 첫째 줄에는 밭의 너비 $n$, 밭의 길이 $m$ ($1 \le n, m \le 1000$), 그리고 관찰한 햇수 $k$ ($1 \le k \le 10000$)가 주어진다. 이어지는 $m$개의 줄에는 각각 $n$개의 정수 $g_{i,j}$ ($i = 1 \dots m$, $j = 1 \dots n$, $0 \le g_{i,j} \le 2^{16}$)가 주어지며, 이는 좌표 $(i, j)$ 구획에서 자라는 카네이션의 수이다.

좌표계는 다음과 같다. 밭은 $0 \le x \le n$, $0 \le y \le m$ 범위를 차지하며, 구획 $(i, j)$는 마주 보는 두 꼭짓점이 $(j-1,\ i-1)$과 $(j,\ i)$인 단위 정사각형이다. 즉 $j$는 가로($x$) 방향, $i$는 세로($y$) 방향을 나타내고, 입력의 첫 번째 줄은 $i = 1$(즉 $0 \le y \le 1$)에 해당한다.

그다음 $k$개의 줄에는 각 해에 그린 다각형이 순서대로 주어진다. 각 다각형은 꼭짓점의 수 $l$ ($3 \le l \le 100$)로 시작하고, 이어서 꼭짓점들의 좌표 $x, y$ ($0 \le x \le n$, $0 \le y \le m$)가 차례대로 주어진다.

각 테스트의 각 해에 대해, 농부가 수확한 카네이션의 수를 한 줄에 하나씩 출력한다.

아래 그림은 위에서 설명한 상황을 나타낸 것이다.