Hallucinogenic Carnations

A farmer has grown hallucinogenic carnations since time immemorial. The carnations grow on a rectangular field divided into equal square parcels. Each parcel grows a certain number of carnations and, remarkably, the very same parcel always grows the very same number of carnations year after year.

On the first day of summer each year the farmer starts the harvest. He draws a polygon on the field. Every vertex of the polygon has integer coordinates, and each side is parallel, perpendicular, or slanted at $45$, $135$, $225$, or $315$ degrees relative to the sides of the field. The polygon is simple: two of its sides share a point only when they are adjacent.

Using this polygon, the farmer harvests the carnations of every parcel at least half of whose area lies inside the polygon. Whatever is not harvested is happily eaten by all sorts of running, flying, and smelly creatures.

How many carnations does the farmer harvest in each successive year?

The first line contains the number of tests $d$ ($1 \le d \le 10$).

The first line of each test contains the field width $n$, the field length $m$ ($1 \le n, m \le 1000$), and the number of observed years $k$ ($1 \le k \le 10000$). Each of the next $m$ lines contains $n$ integers $g_{i,j}$ ($i = 1 \dots m$, $j = 1 \dots n$, $0 \le g_{i,j} \le 2^{16}$): the number of carnations growing on the parcel with coordinates $(i, j)$.

Coordinates work as follows. The field occupies $0 \le x \le n$ and $0 \le y \le m$, and parcel $(i, j)$ is the unit square whose opposite corners are $(j-1,\ i-1)$ and $(j,\ i)$. Thus $j$ is the horizontal ($x$) coordinate and $i$ is the vertical ($y$) coordinate, and the first of the $m$ lines corresponds to $i = 1$ (that is, $0 \le y \le 1$).

The next $k$ lines describe the polygon drawn in each successive year. Each polygon starts with its number of vertices $l$ ($3 \le l \le 100$), followed by the coordinates $x, y$ ($0 \le x \le n$, $0 \le y \le m$) of its consecutive vertices.

For each year of each test, print on its own line the number of carnations the farmer harvested.

The figure below illustrates the situation described above.