Let $(a,b)\le (c,d)$ denote two points $(a,b),(c,d)$ on the plane satisfies $a\le c,b\le d$. There are $n$ events denoted by $n$ distinct points $\{(x_i,y_i){\}}_{i=1}^n$ on the plane. There are $m$ epochs denoted by a rectangle $(r_{i,1},r_{i,2},c_{i,1},c_{i,2})$ where $(r_{i,1},c_{i,1})$ is the bottom-left corner of the rectangle and $(r_{i,2},c_{i,2})$ is the upper-right corner, and it is guaranteed that $(r_{i,1},c_{i,1})\le (r_{i,2},c_{i,2})$. We say epoch $i$ includes event $j$ if and only if $(r_{i,1},c_{i,1})\le (x_j,y_j)\le (r_{i,2},c_{i,2})$.

If two events $i,j$ satisfy $(x_i,y_i)\le (x_j,y_j)$, then the two events constitute an occurrence of sadness. For all events in an epoch, the occurrences of sadness are called the tear of the epoch, and the size of the tear of the epoch is measured by the number of occurrences of sadness. We'd like to compute the size of the tears of the epochs.

Input Specification

The first line contains two integers $n,m$ denoting the number of events and the number of epochs. The second line contains $n$ integers $p_i$, and the $i$-th number denotes event $i$ has coordinate $(i,p_i)$ on the plane. It is guaranteed that $p_i$ is a permutation of $1,2,\dots ,n$. In the following $m$ lines, each line contains four integers $r_{i,1},r_{i,2},c_{i,1},c_{i,2}$ denoting the rectangle corresponding to the epoch.

Output Specification

There are $m$ lines and each line contains an integer. The $i$-th line denotes the size of the tear of epoch $i$.

Sample 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

Sample Output 1

1
4
2
4
4
4
0
0
0

Constraints

For all test cases, $1\le n\le {10}^5$, $1\le m\le 2\times {10}^5$, $1\le r_{i,1},r_{i,2},c_{i,1},c_{i,2}\le n$.

Test Case	$n$	$m$	Additional Constraints
1~3	$10$	$10$	None.
4	$3000$	$3000$
5	$4000$	$4000$
6	$5000$	$5000$
7	$25000$	$25000$	For every epoch $i$, we have $c_{i,1}=1$ and $c_{i,2}=n$.
8	$50000$	$100000$
9	$75000$	$150000$
10	$100000$	$200000$
11	$60000$	$120000$	For any two rectangles representing different epochs, either one is contained in another (the boundaries may overlap) or they are disjoint.
12	$80000$	$160000$
13	$100000$	$200000$
14	$20000$	$20000$	None.
15	$30000$	$30000$
16	$40000$	$40000$
17	$50000$	$50000$
18	$60000$	$60000$
19	$70000$	$70000$
20~22	$100000$	$200000$	There exists at most 50 pairs of events $(i,j)$ ($1\le i<j\le n$) that do not satisfy $(i,p_i)\le (j,p_j)$.
23~25	$100000$	$200000$	None.