Getting in Trouble
By Contest Road to Fortaleza VII 
Brazil
By Contest Road to Fortaleza VII Brazil
Bob went to Nlogonia looking for a new adventure. But, as soon as he arrived, he got in trouble with the creatures of that place as they were not that nice. They had a awkward game and that time was the Bob’s turn. They would drop him in a place and his objective was to get away alive and in time.
As Bob knew that he would be cooked if he had not made a plan in time, he stoled a map of the field he would be dropped in. But, he still did not know where exactly would be left by them. So he had to memorize the whole map to get away from that place alive. Fortunately, the field is a (N + 1) x (M + 1) rectangular grid and the only possible directions was heading north, south, east or west. The only crucial thing in memorizing were the holes, also rectangular. As he should have done it as fast as he could, he could not take a wrong way.
Example of a 6 x 6 grid map with two holes and a possible way to get out.
Now, he is asking you how many ways he could have left that place as fast as possible if the had being dropped in a position (xi, yi) and had to reach position (xf , yf).
The input is composed of several test cases and ends with end of file. Each one describes a map and starts with three integers N, M (1 ≤ N, M ≤ 1000) and H (0 ≤ H ≤ 100), which are, respectively, the size of the grid and the number of holes, as described above. Then, follows H lines, each with four integers xi, yi, xf and yf (0 ≤ xi,xf ≤ N; 0 ≤ yi,yf ≤ M ) describing the bottom left and the upper right corners of a hole. Next follows a integer Q (1 ≤ Q ≤ 100), the number of queries. Then, follows Q lines, each with four integers xi, yi, xf and yf (0 ≤ xi,xf ≤ N; 0 ≤ yi,yf ≤ M ), which are the starting point and the ending point as described above. Between consecutive tests, there is a blank line. It is guaranteed that in a single map, all the holes are disjoint and there is always at least one way to get out.
Your program must output one line for each query of a test case with the number of ways of getting away as fast as possible. As the number can be very large, you must output modulo 109 + 7. Print a blank line after each test case.
| Sample Input | Sample Output |
|
10 10 0 |
184756 |