题目描述
小 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 明白，如果他回答不了这个问题，他也将成为时代的眼泪，请你帮帮他。
输入输出格式
输入格式
从文件 tears.in 中读入数据。
第一行两个整数$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}$，表示每个时代对应的矩形。
输出格式
输出到文件 tears.out 中。
输出$m$行，每行包含一个整数，第$i$行输出第$i$个时代的眼泪的大小。
输入输出样例
输入样例 #1
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
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 imes 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)$。