D. Celestial Sky
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The sky is draped in an invisible coordinate system that will help you find your way anywhere in the universe. Your telescope shows a slice of the sky that resembles this coordinate system, and in it contains a series of $$$N$$$ stars. Note that the coordinates of stars may overlap. You would like to count all the stars within a certain rectangular region in the coordinate system. But, there is a catch. If you detect a black hole, you know that they will eat up everything in the 3x3 box centered at their starting coordinate, so any stars in the vicinity will cease to exist in another 100 million years. Given that you want your stars to be intact in the next 100 million years, please figure out how many such stars are in your query box.

Input

The first line of input contains the positive integers $$$N$$$, $$$M$$$, and $$$Q$$$ ($$$1 \leq N,M,Q \leq 10^5$$$).

The next $$$N$$$ lines each contain two integers $$$x, y$$$ ($$$0 \leq x, y \lt 1000$$$), describing the (not necessarily distinct) coordinates of a star.

The next $$$M$$$ lines each contain two integers $$$x,y$$$ ($$$0 \leq x, y \lt 1000$$$), describing the coordinates of a black hole.

The last $$$Q$$$ lines contain four integers $$$x_1,y_1,x_2,y_2$$$ ($$$0 \leq x_1, y_1, x_2, y_2 \lt 1000$$$), describing the lower-left $$$(x_1,y_1)$$$ and upper-right $$$(x_2,y_2)$$$ corner of the rectangle, which has positive area.

Output

Please output $$$Q$$$ lines, the $$$i$$$-th line containing the number of valid stars in the $$$i$$$-th query rectangle.

Example
Input
12 2 3
1 4
2 5
2 6
4 8
5 3
5 6
5 9
6 2
6 7
7 3
8 3
8 9
2 4
6 8
2 6 3 8
4 2 9 5
2 2 9 9
Output
1
4
8
Note

Note that star and black hole coordinates may overlap, and are not necessarily distinct.