Description
The Great East Japan Earthquake was a magnitude 9.0 undersea megathrust earthquake that occurred off the coast of Japan on Friday, March 11th 2011. Actually, earthquakes are frequently occurring in the world. To understand the distribution of earthquakes, the researchers in Big Research Universal Central of Earthquake (BRUCE) plan to analyze the frequency of the earthquakes in each region in the world.
.png)
Data of the earthquakes are collected from different locations. For ease of understanding, each earthquake is represented by a blue rectangle, whose area indicates the affected range. See Figure 1 for an example.
Each blue rectangle is represented by the coordinates in its lower-left and upper-right corners. The coordinate values are all integers. In the figure, there are three earthquakes, A, B, and C. Earthquake A affects the region (0,1) to (4,5), earthquake B affects the region (1,2) to (6,8), and earthquake C affects the region (3,0) to (7,6). Note that the region (3, 3) to (4, 5) was affected by all the three earthquakes.
Given the data, people would like to consider different regions to live. To find the safest place, one idea is to get the maximum earthquake frequency in each of the considered region. For instance, suppose that the considered region is (2,4) to (8,7), which is represented by the red rectangle in Figure 1. Then the sub-region (3,4) to (4,5) is affected by all three earthquakes, and achieved the maximum frequency of 3.
Your task is to calculate the maximum frequency for any considered region R.
Input
The input begins with t (1 <= t <= 10), the number of test cases. For each case, the first line contains two integers n (1 <= n <= 1,000), which is the number of earthquakes, and Q (1 <= Q <= 1,000), which is the number of considered regions. For the next n lines, each line contains four integers x1, y1, x2, y2 (x1 < x2, y1 < y2, 10-9 <= x1, y1, x2, y2 <= 109), which are the regions of the earthquakes. After that, the next Q lines denote the considered regions, whose format will be the same as the regions of the earthquakes.
Output
For each considered regions, print a line with the maximum earthquake frequency in the region. Print a blank line after the output for each test case.