Invasion

Our world contains many powerful things, but everyone agrees that nothing is of greater power than a war helicopter. Especially the newest model equipped with a flamethrower that can fire in 4 directions simultaneously.

Thus, when the aliens invaded the world, there was no question about what weapon should be used against them.

The invaders have N spaceships, each of which can be represented as a grid-aligned rectangle. These rectangles can overlap. There are M potential target points, where the helicopter can be placed. When a target point is selected, the helicopter flies there and fires its weapon, throwing destructive fire in all four directions (left, right, up, down). These fire beams don't stop until they reach the border of the world and destroy each enemy spaceship that happens to be in their way.

Your job is to write a program that determines for each target point how many spaceships would be destroyed if the helicopter were to shoot its weapon there.

All coordinates (corner points of rectangles, target points) are integers (both X and Y).

If only the border or a corner point of a spaceship's rectangle is hit, it should still be counted. If two or more overlapping spaceships are hit, all of them should be counted. If a spaceship is hit by multiple beams, it should be counted only once. If the helicopter is inside the rectangle of a spaceship, that spaceship should be counted.

For example:

On the left figure, the helicopter is at (3,1), and 4 buildings get destroyed.

On the right figure, the helicopter is at (5,3), and 3 buildings get destroyed.

Input Specification

The first line contains N (the number of spaceships) and M (the number of target points) separated by a space. Each of the following N lines contains four space-separated integers: L, R, T, and B; which are the left, right, top, and bottom coordinates of a spaceship's rectangle (L < R; T < B). Each of the following M lines contains two integers separated by a space: X and Y, the coordinates of a target point.

Input Limits and Constraints

• 1 ≤ N ≤ 100 000;
• 1 ≤ M ≤ 100 000;
• each coordinate is an integer between 0 and 999 999 999 (both included).

Output Specification

The output should contain M lines: for each target point, the number of spaceships destroyed should be printed if that target point is selected.

Sample Input

1. 5 2
2. 0 1 0 2
3. 0 1 3 4
4. 1 3 4 6
5. 2 6 2 5
6. 4 7 1 6
7. 3 1
8. 5 3

download as text file

Output for Sample Input

1. 4
2. 3

download as text file