Sugar and Salt give you a 2D plane. Two points $(x_1, y_1)$ and $(x_2, y_2)$ on the plane form a dominating pair (denoted as $(x_1, y_1) \le (x_2, y_2)$) if and only if $x_1 \le x_2$ and $y_1 \le y_2$. Initially, $n$ distinct points $\{(x_i, y_i)\}_{i=1}^n$ are given on the plane.

You need to answer $m$ queries. Each query provides two points $(x, y)$ and $(x', y')$. You are asked to find the number of pairs $(i, j)$ such that $(x, y) \le (x_i, y_i) \le (x_j, y_j) \le (x', y')$ and $i \neq j$.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers, where the $i$-th integer $p_i$ represents the $i$-th point $(i, p_i)$ initially given on the plane. It is guaranteed that $p_i$ is a permutation of $1$ to $n$.

The following $m$ lines each contain four space-separated integers $x, x', y, y'$, representing a query. It is guaranteed that $(x, y) \le (x', y')$.

Output

Output $m$ lines, where the $i$-th line contains a single integer representing the answer to the $i$-th query.

Examples

Input 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

Output 1

1
4
2
4
4
4
0
0
0

Note

For the first query, the points $(x_i, y_i)$ satisfying $(x, y) \le (x_i, y_i) \le (x', y')$ are $(4, 6), (6, 4), (7, 5), (8, 3)$. The dominating pairs are $(6, 4), (7, 5)$, corresponding to the pair $(6, 7)$.

For the second query, the points $(x_i, y_i)$ satisfying $(x, y) \le (x_i, y_i) \le (x', y')$ are $(2, 8), (3, 7), (4, 6), (5, 2), (6, 4), (7, 5), (8, 3), (9, 1)$. The dominating pairs are $(5, 2), (6, 4)$; $(6, 4), (7, 5)$; $(5, 2), (7, 5)$; and $(5, 2), (8, 3)$, corresponding to the pairs $(5, 6), (6, 7), (5, 7), (5, 8)$.

For the third query, the points $(x_i, y_i)$ satisfying $(x, y) \le (x_i, y_i) \le (x', y')$ are $(5, 2), (6, 4), (8, 3)$. The dominating pairs are $(5, 2), (6, 4)$ and $(5, 2), (8, 3)$, corresponding to the pairs $(5, 6), (5, 8)$.

For the fourth query, the points $(x_i, y_i)$ satisfying $(x, y) \le (x_i, y_i) \le (x', y')$ are $(4, 6), (5, 2), (6, 4), (7, 5), (8, 3)$. The dominating pairs are $(5, 2), (6, 4)$; $(6, 4), (7, 5)$; $(5, 2), (7, 5)$; and $(5, 2), (8, 3)$, corresponding to the pairs $(5, 6), (6, 7), (5, 7), (5, 8)$.

For the fifth query, the points $(x_i, y_i)$ satisfying $(x, y) \le (x_i, y_i) \le (x', y')$ are $(4, 6), (5, 2), (6, 4), (7, 5), (8, 3)$. The dominating pairs are $(5, 2), (6, 4)$; $(6, 4), (7, 5)$; $(5, 2), (7, 5)$; and $(5, 2), (8, 3)$, corresponding to the pairs $(5, 6), (6, 7), (5, 7), (5, 8)$.

For the sixth query, the points $(x_i, y_i)$ satisfying $(x, y) \le (x_i, y_i) \le (x', y')$ are $(1, 9), (2, 8), (3, 7), (4, 6), (5, 2), (6, 4), (7, 5), (8, 3), (9, 1)$. The dominating pairs are $(5, 2), (6, 4)$; $(6, 4), (7, 5)$; $(5, 2), (7, 5)$; and $(5, 2), (8, 3)$, corresponding to the pairs $(5, 6), (6, 7), (5, 7), (5, 8)$.

For the seventh query, the point $(x_i, y_i)$ satisfying $(x, y) \le (x_i, y_i) \le (x', y')$ is $(3, 7)$. There are no dominating pairs.

For the eighth query, there are no points $(x_i, y_i)$ satisfying $(x, y) \le (x_i, y_i) \le (x', y')$. There are no dominating pairs.

For the ninth query, there are no points $(x_i, y_i)$ satisfying $(x, y) \le (x_i, y_i) \le (x', y')$. There are no dominating pairs.

Subtasks

Idea: ccz181078 & nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: nzhtl1477 & ccz181078

For $100 \%$ of the data, $1 \le n \le 10^5$, $1 \le m \le 2 \times 10^5$.