Counting Users in a Rectangular Region

Mokia, a mobile phone company, has developed an advanced user positioning system. Among its impressive features, it can accurately answer questions like "Where is user C located?" down to the millimeter. However, its real high-tech capability lies in answering questions of the form "How many users are there in a given rectangular region?"

The world is modeled as a square region of size \(w \times w\), which is divided into \(1 \times 1\) cells. Each cell has coordinates \((x, y)\) where \(1 \le x, y \le w\). For example, in a \(4 \times 4\) grid, the coordinates range from \(1\) to \(4\) for both \(x\) and \(y\).

Your task is to help Mokia by writing a program to determine how many users are located within a specified rectangular sub-region of the grid. The rectangle is defined by its lower-left and upper-right coordinates.

Note: All formulas must be formatted in \(\LaTeX\). For instance, the grid is of size \(w \times w\) and cell coordinates satisfy \(1 \leq x,y \leq w\).

inputFormat

The input is given in the following format:

w n
x₁ y₁
x₂ y₂
... (n lines in total)
q
x1 y1 x2 y2
x1 y1 x2 y2
... (q lines in total)

Where:

• \(w\) is the size of the grid (the grid is \(w \times w\)).
• \(n\) is the number of users and the next \(n\) lines each contain two integers \(x\) and \(y\), representing the coordinate of a user.
• \(q\) is the number of queries.
• Each query is represented by four integers \(x1, y1, x2, y2\) which denote the lower-left and upper-right coordinates of the rectangular region. It is guaranteed that \(x1 \le x2\) and \(y1 \le y2\).

outputFormat

For each query, output a single integer on a new line indicating the number of users that lie within the specified rectangular region (inclusive of the boundaries).

sample

4 4
1 1
2 2
3 3
4 4
2
1 1 2 2
2 2 4 4

2
3