Your Ways

You live in a small, well-planned rectangular town. Its central area measures $H$ kilometers by $W$ kilometers and is divided into $H \times W$ unit blocks, each of size $1 \times 1\ \text{km}^2$. There are $H + 1$ streets running in the West-to-East direction and $W + 1$ avenues running in the North-to-South direction, so the central area is a rectangle in the plane, as shown below.

Figure 1. The central area of a town with $H = 3$ and $W = 6$.

Each intersection is identified by its coordinates in the plane. In the figure above, the bottom-left corner is intersection $(0, 0)$ and the top-right corner is intersection $(6, 3)$.

Your house is at the bottom-left corner $(0, 0)$ and you want to reach the university at the top-right corner $(W, H)$. To avoid wasting any effort, you only ever walk West-to-East or South-to-North. Walking this way, there are $84$ ways to reach the university in the example above.

You will go to the university for $K$ days. Each morning the city closes some parts of the streets and avenues for cleaning. The closures are always arranged so that no blocked part is reachable from another blocked part using only West-to-East and South-to-North walks; in other words, no single monotone route can pass through two blocked parts.

You still travel using only West-to-East and South-to-North moves. For each day, determine how many ways you can reach the university. Because the count can be very large, report it modulo $2552$.

The first line contains an integer $T$, the number of test cases ($1 \le T \le 5$). Each test case has the following format.

The first line of a test case contains three integers $W$, $H$, and $K$ ($1 \le W \le 1000$; $1 \le H \le 1000$; $1 \le K \le 10000$). $W$ and $H$ give the size of the central area, and $K$ is the number of days you go to the university.

Each of the next $K$ lines describes the blocked parts for one day. Line $i$ (for $1 \le i \le K$) begins with an integer $Q_i$ ($1 \le Q_i \le 100$), the number of blocked parts, followed by $Q_i$ groups of four integers. Each group $A$, $B$, $C$, $D$ ($0 \le A \le C \le W$; $0 \le B \le D \le H$) means that the part connecting intersection $(A, B)$ and intersection $(C, D)$ is blocked. Such a part is always a valid $1$-km segment of a street or avenue, so $C - A \le 1$ and $D - B \le 1$.

For each test case, for each day, print on its own line the number of ways to reach the university modulo $2552$. Hence the output for each test case consists of exactly $K$ lines.