Range Interval Queries

Source: CSES

Version: Phuoc Hung OJ Extended

Problem

Given an array $x_1,\ldots,x_n$, each query gives $a,b,c,d$. Count indices $i$ such that $a\le i\le b$ and $c\le x_i\le d$.

Input

The first line contains $n,q$, the second line contains the array, and each of the next $q$ lines contains $a,b,c,d$.

Output

Print the answer for every query.

Subtasks

Subtask 1 (20%)

• $n\le 30$, number of queries $\le 30$.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, number of queries $\le 3000$.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le 2\cdot10^5$
• $1\le x_i\le10^9$
• $1\le a\le b\le n$
• $1\le c\le d\le10^9$

Example

Input

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

Output

2
0
8
1

Explanation

For the first query the values at positions $2..4$ are [2,4,5]; exactly 2 and 4 lie in $[2,4]$.