[NOI2020] 时代的眼泪

小 L 喜欢与智者交流讨论，而智者也经常为小 L 出些思考题。 这天智者又为小 L 构思了一个问题。智者首先将时空抽象为了一个二维平面，进而将一个事件抽象为该平面上的一个点，将一个时代抽象为该平面上的一个矩形。 为了方便，下面记 $(a, b) \leq (c, d)$ 表示平面上两个点 $(a, b),(c, d)$ 满足 $a \leq c$，$b \leq d$。 更具体地，智者给定了 $n$ 个**事件**，他们用平面上 $n$ 个不同的点 $\{(x_i, y_i)\}^n_{i=1}$ 来表示；智者还给定了 $m$ 个**时代**，每个时代用平面上一个矩形 $(r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2})$ 来表示，其中 $(r_{i,1}, c_{i,1})$ 是矩形的左下角，$(r_{i,2}, c_{i,2})$ 是矩形的右上角，保证 $(r_{i,1}, c_{i,1}) \leq (r_{i,2}, c_{i,2})$。我们称时代 $i$ 包含了事件 $j$ 当且仅当 $(r_{i,1}, c_{i,1}) \leq (x_j, y_j ) \leq (r_{i,2}, c_{i,2})$。 智者认为若两个事件 $i, j$ 满足 $(x_i, y_i) \leq (x_j, y_j)$，则这两个事件形成了一次**遗憾**。而对一个时代内包含的所有事件，它们所形成的遗憾被称为这个**时代的眼泪**，而形成的遗憾次数则称为该时代的眼泪的大小。现在智者想要小 L 计算**每个时代的眼泪的大小**。 小 L 明白，如果他回答不了这个问题，他也将成为时代的眼泪，请你帮帮他。

从标准输入中读入数据。 第一行两个整数 $n, m$，分别表示事件数与时代数。 第二行 $n$ 个整数 $p_i$，其中第 $i$ 个数表示事件 $i$ 在平面上的坐标为 $(i, p_i)$。保证 $p_i$ 为一个 $1$ 到 $n$ 的排列。 之后 $m$ 行，每行四个整数 $r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2}$，表示每个时代对应的矩形。

输出到文件标准输出中。 输出 $m$ 行，每行包含一个整数，第 $i$ 行输出第 $i$ 个时代的眼泪的大小。

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

1
4
2
4
4
4
0
0
0

#### 样例 1 解释 对于时代 $1$，包含的遗憾有 $(6, 7)$（即事件 $6$ 与事件 $7$ 形成的遗憾，下同）。 对于时代 $2$，包含的遗憾有 $(5, 6),(6, 7),(5, 7),(5, 8)$。 对于时代 $3$，包含的遗憾有 $(5, 6),(5, 8)$。 对于时代 $4$，包含的遗憾有 $(5, 6),(6, 7),(5, 7),(5, 8)$。 对于时代 $5$，包含的遗憾有 $(5, 6),(6, 7),(5, 7),(5, 8)$。 对于时代 $6$，包含的遗憾有 $(5, 6),(6, 7),(5, 7),(5, 8)$。 对于时代 $7, 8, 9$，它们均不包含任何遗憾。 #### 样例 2 见选手目录下的 tears/tears2.in 与 tears/tears2.ans。 该样例满足特殊限制 A（具体限制见测试点约束）。 #### 样例 3 见选手目录下的 tears/tears3.in 与 tears/tears3.ans。 该样例满足特殊限制 B（具体限制见测试点约束）。 对于所有测试点：$1 \leq n \leq 10^5$，$1 \leq m \leq 2 \times 10^5$，$1 \leq r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2} \leq n$。 --- ### 测试点约束 每个测试点的具体限制见下表： | 测试点编号 | $n\le $ | $m\le $ | 特殊限制 | | :-: | :-: | :-: | :-: | | $1\sim 3$ | $10$ | $10$ | 无 | | $4$ | $3\times 10^3$ | $3\times 10^3$ | 无 | | $5$ | $4\times 10^3$ | $4\times 10^3$ | 无 | | $6$ | $5\times 10^3$ | $5\times 10^3$ | 无 | | $7$ | $2.5\times 10^4$ | $5\times 10^4$ | $\text{A}$ | | $8$ | $5\times 10^4$ | $10^5$ | $\text{A}$ | | $9$ | $7.5\times 10^4$ | $1.5\times 10^5$ | $\text{A}$ | | $10$ | $10^5$ | $2\times 10^5$ | $\text{A}$ | | $11$ | $6\times 10^4$ | $1.2\times 10^5$ | $\text{B}$ | | $12$ | $8\times 10^4$ | $1.6\times 10^5$ | $\text{B}$ | | $13$ | $10^5$ | $2\times 10^5$ | $\text{B}$ | | $14$ | $2\times 10^4$ | $4\times 10^4$ | 无 | | $15$ | $3\times 10^4$ | $6\times 10^4$ | 无 | | $16$ | $4\times 10^4$ | $8\times 10^4$ | 无 | | $17$ | $5\times 10^4$ | $10^5$ | 无 | | $18$ | $6\times 10^4$ | $1.2\times 10^5$ | 无 | | $19$ | $7\times 10^4$ | $1.4\times 10^5$ | 无 | | $20\sim 22$ | $10^5$ | $2\times 10^5$ | $\text{C}$ | | $23\sim 25$ | $10^5$ | $2\times 10^5$ | 无 | 特殊限制 A：对于所有时代 $i$ 有 $c_{i,1} = 1, c_{i,2} = n$。 特殊限制 B：任意两个不同时代所代表的矩形，它们要么是包含关系（一个矩形在另一个矩形内，边界允许重合），要么是相离关系（两矩形不包含共同点，边界不允许重合）。 特殊限制 C：最多有 $50$ 对事件 $(i, j)(1 \leq i < j \leq n)$ 不满足 $(i, p_i) \leq (j, p_j)$。