Counting rectangles

You have $n$ rectangles; rectangle $i$ has height $h_i$ and width $w_i$. There are $q$ queries, each with numbers $h_s, w_s, h_b, w_b$. Find the total area $\sum h_i w_i$ of all rectangles with $h_s < h_i < h_b$ and $w_s < w_i < w_b$ (strict inequalities). Rectangles cannot be rotated.

The first line contains $n$ and $q$ ($1 \le n, q \le 10^5$). The next $n$ lines contain $h_i$ and $w_i$ ($1 \le h_i, w_i \le 1000$). The next $q$ lines contain $h_s$, $w_s$, $h_b$, $w_b$ ($1 \le h_s < h_b \le 1000$, $1 \le w_s < w_b \le 1000$).

For every query print one number on a separate line.

The sizes are small: build a $1000 \times 1000$ table where $c_{h,w}$ is the total area of rectangles with height $h$ and width $w$. With its 2D prefix sums every query is the sum over rows $h_s + 1 \ldots h_b - 1$ and columns $w_s + 1 \ldots w_b - 1$, in $O(1)$.

The inequalities are strict — a rectangle on the border is not counted. The answer reaches $10^{11}$ — a 64-bit type is needed. In the first example only $2 \times 3$ fits: the answer is $6$.

Source: Codeforces, problem 1722E.