Your Ways
Your Ways
You live in a small well-planned rectangular town in Phuket. The size of the central area of the town is H kilometers × W kilometers. The central area is divided into HW unit blocks, each of size 1×1 km^2. There are H+1 streets going in the West to East direction, and there are W+1 avenue going in the North-South direction. The central area can be seen as a rectangle on the plane, as shown below.
Figure 1. The central area for a town where H = 3, and W = 6.
We can identify each intersection by its co-ordinate on the plane. For example, on 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 (i.e., intersection (0, 0)) and you want to go to the university at the top-right corner (i.e., intersection (W, H)). More over, you only want to go to the university with wasting any efforts; therefore, you only want to walk from West-to-East and South-to-North directions. Walking this way, in the example above there are 84 ways to reach the university.
You want to go to the university for K days. Things get more complicated when each morning, the city blocks parts of streets and avenues to do some cleaning. The blocking is done in such a way that it is not possible to reach parts of the streets or avenues which is blocked from some other part which is blocked as well through any paths containing only West-to-East and South-to-North walks.
You still want to go to the university using the same West-to-East and South-to-North strategy. You want to find out for each day, how many ways you can reach the university by only walking West-to-East and South-to-North. Since the number can be very big, we only want the result modulo 2552.
Входные данные
The first line contains an integer T, the number of test cases (1 ≤ T ≤ 5). Each test case is in the following format.
The first line of each test case contains 3 integers: W, H, and K (1 ≤ W ≤ 1000, 1 ≤ H ≤ 1000, 1 ≤ K ≤ 10000). Wand H specify the size of the central area. K denotes the number of days you want to go to the university.
The next K lines describe the information on broken parts of streets and avenues. More specifically, line 1+i, for 1 ≤ i ≤ K, starts with an integer Q_i (1 ≤ Q_i ≤ 100) denoting the number of parts which are blocked. Then Q_i sets of 4 integers describing the blocked parts follow. Each part is described with 4 integers, A, B, C, and D (0 ≤ A ≤ C ≤ W,0 ≤ B ≤ D ≤ H) meaning that the parts connecting intersection (A, B) and (C, D) is blocked. It is guaranteed that that part is a valid part of the streets or avenues, also C-A ≤ 1, and D-B ≤ 1, i.e., the part is 1 km long.
Выходные данные
For each test case, for each day, your program must output the number of ways to go to the university modulo 2552 on a separate line. i.e., the output for each test case must contains K lines.
Пример
2 2 2 3 1 0 0 0 1 2 1 0 2 0 0 2 1 2 1 1 1 2 1 100 150 2 1 99 150 100 150 2 99 150 100 150 100 149 100 150
126 105 2081 2123 749 348 484 228 616 1452 814 134 1539 788 1760 597 2408 572 1496 2462 1496 2420 998 1452 1496 1496 858 1032 1901 1927 684 1422 727 86 1833 286 1496 1496 1496 968 52 422 2454 1936 946 1084 2068 1100 506 1496 2126 1349 2167 1580 1419 1232 916 1508 880 1583 1232 883 1972 1623 2056 364 1073 2024 1830 1639 1966 2420 676 704 2301 792 1760 2536 486 2386 2464 1542 1090 0 600 2068 1874 1760 56 432 2308 2232 286 2182 1144 858 566 616 220 1496 1023 1196 1799 1728 2448 2018 1452 660 847 785 386 1182 96 1163 2442 2032 1150 1863 2110 1187 2394 172 974 680 2141 251 1967 1522 1804 924 728 855 1800 1480 196 808 2051 154 1892 436 2499 2355 886 56 834 2179 945 632 123 1484 1803 1563 732 2232 80 1342 47 42 944 2301 2312 460 1078 1360 1384 1856 2239 1184 266 878 1444 2111 740 273 1620 2352 303 2292 2270 1190 1060 1598 0 1264 1886 1060 609 2361 136 1977 2422 1188 1528 272 1400 1006 2538 768 917 2032 1376 1793 2127 1383 1008 1348 1460 1457 1889 1062 144 2041 1384 737 1692 784 2212 1930 1051 ...