Traveling in Cells 2
小青鱼有一位名叫绾绾的朋友。绾绾在一张很大的网格上:左下角格子的坐标为 (0,0),右上角格子的坐标为 (106,106)。格子的坐标均为整数。
最初有 n 个障碍,第 i 个障碍在 (xi(O),yi(O))。所有初始障碍都不在网格边界上,即 0<xi(O),yi(O)<106。
绾绾每次只能向上移动一格,或者向右移动一格;任何时候都不能位于有障碍的格子。
形式化地,从 (xs,ys) 到 (xt,yt) 的合法路径为一个格子序列
P:(a1,b1),(a2,b2),…,(aℓ,bℓ),
满足:
- (a1,b1)=(xs,ys),(aℓ,bℓ)=(xt,yt)。
- 对每个 1≤i<ℓ,恰有以下一种情况成立:ai+1=ai, bi+1=bi+1;或者 ai+1=ai+1, bi+1=bi。
- 对每个 1≤i≤ℓ,(ai,bi) 都没有障碍。

绾绾不能经过有障碍的格子。此外,一些原本没有障碍的格子也不会出现在任何一条合法路径上。任何无法出现在从 (0,0) 到 (106,106) 的任意合法路径中的格子,都会变成新的障碍。 重复这一过程,直到每个自由格子(即没有障碍的格子)都能出现在至少一条这样的合法路径中。
下图中,红点是最初的障碍,橙点是在这一过程中新增的障碍。

补完所有额外障碍后,小青鱼要回答 q 次行走询问。第 i 次询问考虑从 (xi(s),yi(s)) 到 (xi(t),yi(t)) 的所有合法路径,求被其中至少一条路径经过的不同格子数。
形式化地,一个格子 (x,y) 被计数,当且仅当存在一条合法路径 P:(a1,b1),…,(aℓ,bℓ),其起点为 (xi(s),yi(s)),终点为 (xi(t),yi(t)),并且某个 1≤j≤ℓ 满足 (aj,bj)=(x,y)。计数包含合法的起点和终点;若不存在路径,答案为 0。所有询问都在同一张补完障碍的网格上进行,询问不会修改网格。
输入格式
第一行两个整数 n,q(1≤n,q≤105)。
接下来 n 行描述初始障碍。第 i 行两个整数 xi(O),yi(O)(1≤xi(O),yi(O)<106),表示第 i 个障碍的坐标。
接下来 q 行描述询问。第 i 行四个整数 xi(s),yi(s),xi(t),yi(t),满足
$$1\le x_i^{(s)}\le x_i^{(t)}<10^6,\qquad
1\le y_i^{(s)}\le y_i^{(t)}<10^6.$$
本题输入只有一组数据。原题没有给出初始障碍坐标互异的保证;重复坐标表示同一个被阻挡的格子。
输出格式
对每次询问,按输入顺序输出一行一个整数,表示答案。答案可能超过 32 位有符号整数范围。
原样例 1
3 3
2 3
3 2
4 4
1 1 5 5
3 4 5 5
3 3 4 5
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
28
11
样例说明
第一个样例最初有三个障碍(红点),补障碍过程又增加两个障碍(橙点)。下图从左到右对应其三个询问;蓝点表示被至少一条询问路径经过的格子。

第三次询问中,起点 (3,3) 已被补为障碍,因此没有合法路径,答案为 0。