eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Your Ways

Your Ways

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

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 (1T5). Each test case is in the following format.

The first line of each test case contains 3 integers: W, H, and K (1W1000, 1H1000, 1K10000). 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 1iK, starts with an integer Q_i (1Q_i100) 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 (0ACW,0BDH) 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-A1, and D-B1, 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.

Приклад

Вхідні дані #1
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
Вихідні дані #1
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
...