Description

It seems ordinary hard problems cannot stump this gardener. The king decided to exhaust his strength with a war of attrition: "Young man, there are $n$ trees in my garden, and each tree can be represented by an integer coordinate. Soon, my $m$ knights will come in turns to ask you how many trees lie inside a certain rectangle. If you cannot answer immediately and correctly, be ready to leave!" After saying this, the king stormed off.

Now it was the gardener's turn to be dumbfounded—he had not prepared for such a problem. Fortunately, as the president of the "National Gardeners Protection Alliance"—you—can become his last lifeline.

Input Format

The first line contains two integers $n, m$, representing the number of trees and the number of queries.

The next $n$ lines each contain two integers $x, y$, indicating that there is a tree at coordinate $(x, y)$. It is possible that two trees share the same coordinate.

The next $m$ lines each contain four integers $a, b, c, d$, describing a query: count how many trees are inside the rectangle with lower-left corner $(a, b)$ and upper-right corner $(c, d)$, including the boundary.

Output Format

For each query, output a single integer on its own line indicating the answer.

3 1
0 0 
0 1
1 0
0 0 1 1

3

Hint

Constraints and Conventions

• For $30\%$ of the testdata, it is guaranteed that $n, m \leq 10$.
• For $100\%$ of the testdata, it is guaranteed that $0 \leq n \leq 5 \times 10^5$, $1 \leq m \leq 5 \times 10^5$, $0 \leq x, y, a, b, c, d \leq 10^7$, $a \leq c$, $b \leq d$.

Translated by ChatGPT 5