Little L likes to discuss problems with a wise man, and the wise man often poses thought-provoking questions to Little L.

One day, the wise man conceived a new problem for Little L. The wise man first abstracted space-time into a two-dimensional plane, then abstracted an event as a point on this plane, and an era as a rectangle on this plane.

For convenience, we denote $(a, b) \le (c, d)$ to mean that for two points $(a, b)$ and $(c, d)$ on the plane, $a \le c$ and $b \le d$ are satisfied.

More specifically, the wise man provided $n$ events, represented by $n$ distinct points $\{(x_i, y_i)\}_{i=1}^n$ on the plane. The wise man also provided $m$ eras, each represented by a rectangle $(r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2})$ on the plane, where $(r_{i,1}, c_{i,1})$ is the bottom-left corner and $(r_{i,2}, c_{i,2})$ is the top-right corner of the rectangle, with $(r_{i,1}, c_{i,1}) \le (r_{i,2}, c_{i,2})$ guaranteed. We say that era $i$ contains event $j$ if and only if $(r_{i,1}, c_{i,1}) \le (x_j, y_j) \le (r_{i,2}, c_{i,2})$.

The wise man believes that if two events $i$ and $j$ satisfy $(x_i, y_i) \le (x_j, y_j)$, then these two events form a "regret." The set of all regrets formed by events contained within an era is called the "tears of that era," and the number of such regrets is called the size of the tears of that era. Now, the wise man wants Little L to calculate the size of the tears for each era.

Little L understands that if he cannot answer this question, he will also become a "tear of the era." Please help him.

Input

The first line contains two integers $n$ and $m$, representing the number of events and the number of eras, respectively.

The second line contains $n$ integers $p_i$, where the $i$-th number indicates that the coordinates of event $i$ on the plane are $(i, p_i)$. It is guaranteed that $p_i$ is a permutation of $1$ to $n$.

Following this are $m$ lines, each containing four integers $r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2}$, representing the rectangle corresponding to each era.

Output

Output $m$ lines, each containing one integer, where the $i$-th line outputs the size of the tears for the $i$-th era.

Examples

Input 1

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 era 1, the regrets contained are $(6, 7)$ (i.e., the regret formed by event 6 and event 7, and so on).

For era 2, the regrets contained are $(5, 6), (6, 7), (5, 7), (5, 8)$.

For era 3, the regrets contained are $(5, 6), (5, 8)$.

For era 4, the regrets contained are $(5, 6), (6, 7), (5, 7), (5, 8)$.

For era 5, the regrets contained are $(5, 6), (6, 7), (5, 7), (5, 8)$.

For era 6, the regrets contained are $(5, 6), (6, 7), (5, 7), (5, 8)$.

For eras 7, 8, and 9, they do not contain any regrets.

Input 2

(See tears/tears2.in)

Output 2

(See tears/tears2.ans)

Note

This example satisfies special constraint A (see the test point constraints for details).

Input 3

(See tears/tears3.in)

Output 3

(See tears/tears3.ans)

Note

This example satisfies special constraint B (see the test point constraints for details).

Constraints

For all test points: $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$.

Special constraint A: For all eras $i$, $c_{i,1} = 1$ and $c_{i,2} = n$.

Special constraint B: For any two different eras, the rectangles they represent are either in an inclusion relationship (one rectangle is inside the other, boundaries are allowed to coincide) or are disjoint (the two rectangles share no common points, boundaries are not allowed to coincide).

Special constraint C: There are 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)$.