Little Cyan Fish 有一个朋友叫 Wanwan。Wanwan 在一个巨大的网格上。左下角的坐标是 $(0, 0)$，右上角的坐标是 $(10^6, 10^6)$。

最初，网格上有 $n$ 个障碍物，第 $i$ 个障碍物位于 $(x_i^{(O)}, y_i^{(O)})$。所有障碍物都不在网格边界上，即 $0 < x_i^{(O)}, y_i^{(O)} < 10^6$。

Wanwan 每次只能向上或向右移动一步。在任何时候，Wanwan 都不能占据包含障碍物的单元格。

形式化地，从单元格 $(x_s, y_s)$ 到单元格 $(x_t, y_t)$ 的路径 $P$ 可以表示为一系列单元格 $P : (a_1, b_1), (a_2, b_2), \dots, (a_\ell, b_\ell)$，其中：

• $a_1 = x_s, b_1 = y_s$ 且 $a_\ell = x_t, b_\ell = y_t$。
• 对于所有 $1 \le i < \ell$，以下条件之一成立：
  1. $a_{i+1} = a_i$ 且 $b_{i+1} = b_i + 1$；
  2. $a_{i+1} = a_i + 1$ 且 $b_{i+1} = b_i$。
• 对于所有 $1 \le i \le \ell$，$(a_i, b_i)$ 不是障碍物。

图 1：一条合法的路径。障碍物用红点标记。

当然，Wanwan 不能访问任何包含障碍物的单元格。然而，还有一些单元格没有被任何合法路径覆盖。任何不能成为从 $(0, 0)$ 到 $(10^6, 10^6)$ 的任何合法路径一部分的单元格都会变成一个新的障碍物。这个过程会不断重复，直到每个空闲单元格（即不包含障碍物的单元格）都能被包含在从 $(0, 0)$ 到 $(10^6, 10^6)$ 的某条合法路径 $P$ 中。

例如，在下图中，最初出现的障碍物用红点标记，过程中添加的障碍物用橙色点标记。

图 2：添加所有额外障碍物后的网格。

接下来，在添加所有额外障碍物后，Little Cyan Fish 需要完成 $q$ 次随机游走查询。对于第 $i$ 次查询，Little Cyan Fish 考虑从 $(x_i^{(s)}, y_i^{(s)})$ 到 $(x_i^{(t)}, y_i^{(t)})$ 的所有路径。Little Cyan Fish 想知道有多少个单元格至少被其中一条路径访问过。

形式化地，如果存在一条路径 $P : (a_1, b_1), \dots, (a_\ell, b_\ell)$，使得 $(a_1, b_1) = (x_i^{(s)}, y_i^{(s)})$，$(a_\ell, b_\ell) = (x_i^{(t)}, y_i^{(t)})$，且对于某个 $1 \le j \le \ell$ 有 $(a_j, b_j) = (x, y)$，则单元格 $(x, y)$ 应被计入。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)。

接下来的 $n$ 行描述了最初存在的所有障碍物。第 $i$ 行包含两个整数 $x_i^{(O)}$ 和 $y_i^{(O)}$ ($1 \le x_i^{(O)}, y_i^{(O)} < 10^6$)，表示第 $i$ 个障碍物的坐标。

接下来的 $q$ 行描述了所有查询。第 $i$ 行包含四个整数 $x_i^{(s)}, y_i^{(s)}, x_i^{(t)}$ 和 $y_i^{(t)}$ ($1 \le x_i^{(s)} \le x_i^{(t)} < 10^6, 1 \le y_i^{(s)} \le y_i^{(t)} < 10^6$)，表示第 $i$ 个任务。

输出格式

对于每个任务，输出一行，包含一个整数，表示答案。

样例

样例输入 1

3 3
2 3
3 2
4 4
1 1 5 5
3 4 5 5
3 3 4 5

样例输出 1

20
4
0

样例输入 2

8 2
2 2
2 5
3 5
4 1
5 4
6 1
7 3
8 2
1 1 9 5
5 1 8 5

样例输出 2

28
11

说明

在第一个样例中，最初有三个障碍物（用红点标记），在 Wanwan 的第一次行程后又添加了两个障碍物（用橙色点标记）。

图 3：对应第一个样例的图。

对于每个查询，所有可访问的单元格都用蓝色标记。在第三个查询中，由于 $(x_i^{(s)}, y_i^{(s)})$ 已经被障碍物占据，因此没有任何单元格可以通过任何路径访问。