Remember the problem "Buy Your House" in Phuket regional, 2009?
Back in Taiwan, Kelvin recieves a similar offer - that is, he is also offered to choose a certain rectangle region that contains exactly one house offered by the real estate.
However this time the real estate development company is a much larger and renowned one, therefore the number of houses they offer is also much bigger. In fact, there can be up to 1000 houses!!
The deal was made on the afternoon of 9/4/2010, and Kelvin is required to make his decision (on what rectangle he should pick) in 5 hours. Being a rather passionate programmer he decided to write a program to solve the problem. But being a rather unskillful one at the same time, he failed to write a program that actually function correctly during the 5 hours, therefore losing the nice deal.
Now, can you solve this problem?
The original problem can be viewed here, note that the only change from the original problem is the input size.
Input will start with an integer T, the number of test cases. Each of the test cases starts with two integers W and H (1 <= W, H <= 1000000000), width and height of the land and the next line contains an integer N (1 <= N <= 1000), the number of houses in the land. Each of the next N lines will contain four integer x1, y1, x2, y2 ( 0 <= x1 < x2 <= W and 0 <= y1 < y2 <= H ), which describes the location of the house. Note that no house can overlap with another house and all the given coordinates will be non negative integers.
For each input, print a single line of the form “Case #: W”, where ‘#’ will be replaced by the case number and W will be replaced by the number of ways you can choose your land. Here W can be very large, so you should print the number of ways modulo 1000000007 as W.
2 3 3 1 1 1 2 2 10 10 2 1 1 4 4 6 6 8 8
Case 1: 16 Case 2: 429
Migrated from old NTUJ.
revised by kelvin, original from phuket regional 2009
| No. | Testdata Range | Score |
|---|