CF1722E.Counting Rectangles

You have $n$ rectangles, the $i$-th rectangle has height $h_i$ and width $w_i$.

You are asked $q$ queries of the form $h_s \ w_s \ h_b \ w_b$.

For each query output, the total area of rectangles you own that can fit a rectangle of height $h_s$ and width $w_s$ while also fitting in a rectangle of height $h_b$ and width $w_b$. In other words, print $\sum h_i \cdot w_i$ for $i$ such that $h_s \lt h_i \lt h_b$ and $w_s \lt w_i \lt w_b$.

Please note, that if two rectangles have the same height or the same width, then they cannot fit inside each other. Also note that you cannot rotate rectangles.

Please note that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

你有 $n$ 个矩形，其中第 $i$ 个矩形的高度为 $h_i$，宽度为 $w_i$。

接下来会有 $q$ 个查询，每个查询的形式为 $h_s \ w_s \ h_b \ w_b$。

对于每个查询，请输出：你所拥有的、既能容纳一个高度为 $h_s$、宽度为 $w_s$ 的矩形，又能被完全放入一个高度为 $h_b$、宽度为 $w_b$ 的矩形中的所有矩形的总面积。换言之，对所有满足 $h_s \lt h_i \lt h_b$ 且 $w_s \lt w_i \lt w_b$ 的下标 $i$，计算并输出 $\sum h_i \cdot w_i$。

请注意：若两个矩形高度相等或宽度相等，则它们无法互相嵌套（即不能“放入”对方）。此外，矩形不可旋转。

还请注意：某些测试用例的答案可能超出 32 位整数范围，因此请在编程语言中至少使用 64 位整数类型（例如 C++ 中的 long long）。

The first line of the input contains an integer $t$ ($1 \leq t \leq 100$) — the number of test cases.

The first line of each test case two integers $n, q$ ($1 \leq n \leq 10^5$; $1 \leq q \leq 10^5$) — the number of rectangles you own and the number of queries.

Then $n$ lines follow, each containing two integers $h_i, w_i$ ($1 \leq h_i, w_i \leq 1000$) — the height and width of the $i$-th rectangle.

Then $q$ lines follow, each containing four integers $h_s, w_s, h_b, w_b$ ($1 \leq h_s \lt h_b,\ w_s \lt w_b \leq 1000$) — the description of each query.

The sum of $q$ over all test cases does not exceed $10^5$, and the sum of $n$ over all test cases does not exceed $10^5$.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 100$）——测试用例的数量。

每个测试用例的第一行包含两个整数 $n, q$（$1 \leq n \leq 10^5$；$1 \leq q \leq 10^5$）——你拥有的矩形数量以及查询数量。

接下来是 $n$ 行，每行包含两个整数 $h_i, w_i$（$1 \leq h_i, w_i \leq 1000$）——第 $i$ 个矩形的高度和宽度。

然后是 $q$ 行，每行包含四个整数 $h_s, w_s, h_b, w_b$（$1 \leq h_s \lt h_b,\ w_s \lt w_b \leq 1000$）——每个查询的描述。

所有测试用例中 $q$ 的总和不超过 $10^5$，所有测试用例中 $n$ 的总和也不超过 $10^5$。

For each test case, output $q$ lines, the $i$-th line containing the answer to the $i$-th query.

对于每个测试用例，输出 $q$ 行，其中第 $i$ 行包含第 $i$ 个查询的答案。

In the first test case, there is only one query. We need to find the sum of areas of all rectangles that can fit a $1 \times 1$ rectangle inside of it and fit into a $3 \times 4$ rectangle.

Only the $2 \times 3$ rectangle works, because $1 \lt 2$ (comparing heights) and $1 \lt 3$ (comparing widths), so the $1 \times 1$ rectangle fits inside, and $2 \lt 3$ (comparing heights) and $3 \lt 4$ (comparing widths), so it fits inside the $3 \times 4$ rectangle. The $3 \times 2$ rectangle is too tall to fit in a $3 \times 4$ rectangle. The total area is $2 \cdot 3 = 6$.

在第一个测试用例中，仅有一个查询。我们需要求出所有能容纳一个 $1 \times 1$ 矩形、且自身又能被容纳于一个 $3 \times 4$ 矩形内的矩形的面积之和。

只有 $2 \times 3$ 矩形满足条件，因为 $1 \lt 2$（高度比较）且 $1 \lt 3$（宽度比较），因此 $1 \times 1$ 矩形可放入其中；同时 $2 \lt 3$（高度比较）且 $3 \lt 4$（宽度比较），因此该矩形可放入 $3 \times 4$ 矩形内。而 $3 \times 2$ 矩形高度过大，无法放入 $3 \times 4$ 矩形中。总面积为 $2 \cdot 3 = 6$。