题目描述

给出 $n$ 个矩形，其中第 $i$个矩形的高为 $hi$，宽为 $wi$。现要处理 $q$ 个查询请求，每个查询由 $hs$、$ws$、$hb$、$wb$ 四个整数组成。

每次查询需从 $n$ 个矩形中找出符合如下要求的矩形 $s$：高 $hb$ 宽 $wb$ 的矩形能容纳矩形 $s$，同时 $s$ 能容纳高 $hs$ 宽 $ws$ 的矩形（如下图所示）。

试计算所有符合要求的 $s$ 的面积总和。 注意:如果两个矩形具有相同的高度或宽度，那么它们就不能相互容纳。另外矩形不能旋转。

输入描述

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 10^3$, $1 \le q \le 10^3$)，表示矩形的数量和查询的次数。

接下来的 $n$ 行每行包含两个整数 $hi$ 和 $wi$ ($1 \le hi, wi \le 1000$)，表示第 $i$ 个矩形的高度和宽度。

接下来的 $q$ 行每行包含四个整数 $hs$, $ws$, $hb$, $wb$ ($1 \le hs < hb \le 1000$, $1 \le ws < wb \le 1000$)，表示查询的高度范围 $[hs, hb)$ 和宽度范围 $[ws, wb)$。

输出描述

一个整数，表示答案。

2 1
2 3
3 2
1 1 3 4

6

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

41
9
0
54
4

3 1
999 999
999 999
999 998
1 1 1000 1000

2993004

数据范围与提示

$100\%$ 的数据

• $1 \leq n \leq 10^3$
• $1 \leq q \leq 10^3$
• $1 \leq h_i, w_i \leq 1000$

对于样例 $1$ 解释

我们需要找出所有能容纳 $1$ * $1$ 同时又能被 $3$ * $4$ 容纳的矩形的面积之和。只有 $2$ * $3$ 的矩形可以，因为 $1 \le 3$，所以 $1$ * $1$ 的矩形可以放入 $2$ * $3$ ；$2 \le 3$ 且 $3 \le 4$ ，所以 $2$ * $3$的矩形可以容纳 $3$ * $4$。

$3$ * $2$ 的矩形虽然能容纳 $1$ * $1$ 的矩形；但太高，无法放入 $3$ * $4$ 的矩形中总面积为$2$ * $3$ = $6$.