你有$$$n$$$个矩形,第$$$i$$$个矩形的高度为$$$h_i$$$,宽度为$$$w_i$$$。
系统会向您询问 $$$q$$$ 形式的查询 $$$h_s \ w_s \ h_b \ w_b$$$。
对于每个查询输出,您拥有的矩形的总面积可以适合高度为 $$$h_s$$$ 和宽度为 $$$w_s$$$ 的矩形,同时也适合高度为 $$$h_b$$$ 和宽度为 $$$w_b$$$ 的矩形。换句话说,打印 $$$\sum h_i \cdot w_i$$$ 对于 $$$i$$$,使得 $$$h_s < h_i < h_b$$$ 和 $$$w_s < w_i < w_b$$$。
请注意,如果两个矩形具有相同的高度或相同的宽度,那么它们就无法相互装入。另请注意,您无法旋转矩形。
请注意,某些测试用例的答案不适合 32 位整数类型,因此您应该在编程语言中至少使用 64 位整数类型(例如 C++ 的 long long)。
输入
输入的第一行包含一个整数 $$$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 < h_b,\ w_s < w_b \leq 1000$$$) - 每个查询的描述。
所有测试用例的 $$$q$$$ 总和不超过 $$$10^5$$$,所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出 $$$q$$$ 行,第 $$$i$$$ 行包含第 $$$i$$$ 查询的答案。
示例
输入 #1
3 2 1 2 3 3 2 1 1 3 4 5 5 1 1 2 2 3 3 4 4 5 5 3 3 6 6 2 1 4 5 1 1 2 10 1 1 100 100 1 1 3 3 3 1 999 999 999 999 999 998 1 1 1000 1000
输出 #1
6 41 9 0 54 4 2993004
注意
在第一个测试用例中,只有一个查询。我们需要找到可以容纳 $$$1 \times 1$$$ 矩形并容纳 $$$3 \times 4$$$ 矩形的所有矩形的面积总和。
只有 $$$2 \times 3$$$ 矩形有效,因为 $$$1 < 2$$$ (比较高度)和 $$$1 < 3$$$ (比较宽度),因此 $$$1 \times 1$$$ 矩形适合内部,而 $$$2 < 3$$$ (比较高度)和 $$$3 < 4$$$ (比较宽度)宽度),因此它适合 $$$3 \times 4$$$ 矩形。 $$$3 \times 2$$$ 矩形太高,无法放入 $$$3 \times 4$$$ 矩形中。总面积为 $$$2 \cdot 3 = 6$$$。