题目描述

你有 $n$ 个矩形，第 $i$ 个矩形具有高度 $h_i$ 和宽度 $w_i$。

我们向您询问许多次有关成对的大小矩形的高和宽 $h_s,w_s,h_b,w_b$ 的问题。（高=height，宽=width，小=small，大=big，熟悉英文的话，很多记号都很好记）

对于每个询问，你需要找出前述 $n$ 个矩形中既能装下高度为 $h_s$ 宽度为 $w_s$ 的矩形，又能被装进高度为 $h_b$ 宽度为 $w_b$ 的矩形的矩形，输出这些矩形的面积和。换句话说，每次查询会给你 $h_s,w_s,h_b,w_b$，你需要输出 $∑_{i=1}^n h_i⋅w_i$，求和号内的 $i$ 需满足 $h_s<h_i<h_b，w_s<w_i<w_b$。

简而言之，你一开始有 $n$ 个矩形，然后每次询问给你一对矩形，一大一小。问你：之前的 $n$ 个矩形有哪些能装入这一大一小的矩形，请输出他们的面积和。

请注意，如果两个矩形具有相同的高度或相同的宽度，则它们不能相互装入。还要注意，不能旋转矩形。

某些测试用例的答案可能超过 $32$ 位整数类型，因此您应该在编程语言中至少使用 $64$ 位整数类型。

输入格式

输入的第一行包含整数 $t(1≤t≤100)$ 代表测试用例数。

每个测试用例的第一行是两个整数 $n,q(1≤n≤10^5，1≤q≤10^5)$ 代表您拥有的矩形数和查询数。

然后是 $n$ 行，每行包含两个整数 $h_i,w_i(1≤h_i,w_i≤1000)$ 代表第 $i$ 个矩形的高度和宽度。

然后是 $q$ 行，每行包含四个整数 $h_s,w_s,h_b,w_b(1≤h_s<h_b≤1000，1≤w_s<w_b≤1000)$ 依次代表每个查询。

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

输出格式

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

测试样例

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

6
41
9
0
54
4
2993004

样例说明

在第一个测试用例中，只有一个查询。给出的小矩形为 $1×1$，大矩形为 $3×4$。我们需要在之前给出的 $n=2$ 个矩形中找到所有可以装下 $1×1$ 的矩形（黑色），并且可以被装进 $3×4$ 的矩形（黑色）的矩形的面积和。

题目共给出了两个矩形，只有 $2×3$ 矩形（蓝色）可行，因为 $1<2$（高度）和 $1<3$（宽度），所以 $1×1$ 的矩形可以装入小矩形内部，$2<3$（高度）和 $3<4$（宽度），因此可以被装入大矩形内部。

$3×2$ 矩形（绿色）太高，无法被装入 $3×4$ 的大矩形。

总面积为 $2×3=6$。