F. The Spirit-Oak's Resonance
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After narrowly escaping the Beast's game, the three friends found themselves in a vast, ancient grove dominated by colossal, glowing Spirit-Oaks. These trees, according to Abd-Elmohaymen's ever-present "Unusual Flora of the Unknown" guide, resonate with different frequencies of spirit energy, measured by unique 'Resonance Values'. The forest was divided into $$$N$$$ distinct segments, and each segment $$$i$$$ had a Spirit-Oak with a specific resonance value $$$A_i$$$.

Their immediate goal was to find a 'Resonance Core' – a mystical artifact that required a precise combination of spirit energies to activate. The guide indicated that the Core would only appear if they could accurately determine the total 'strength' of a particular range of spirit energies within a specific section of the forest.

Periodically, a query would appear on a shimmering leaf: "How many Spirit-Oaks within segments $$$L$$$ to $$$R$$$ (inclusive) possess a Resonance Value between $$$X$$$ and $$$Y$$$ (inclusive)?"

Omar quickly realized this wasn't just about counting individual trees, but about summing up the presence of all trees whose resonance fell within a specific range. They knew the forest segments stretched for miles, and there would be many such queries. Only an efficient method would allow them to progress.

Can you help them calculate, for each query, the total count of Spirit-Oaks whose Resonance Values fall within the specified range $$$[X,Y]$$$ in the given forest segment $$$[L,R]$$$ ?

Input

The first line contains two integers $$$N (1 \le N \le 10^5)$$$, the number of forest segments, and $$$Q (1 \le Q \le 10^5 )$$$, the number of queries.

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \le A_i \le 10^5$$$), representing the Resonance Value of the Spirit-Oak in each segment.

The next $$$Q$$$ lines each contain four integers $$$L,R,X,Y (1 \le L \le R \le N, 1 \le X \le Y \le 10^5 )$$$, representing the start and end of the forest segment, and the lower and upper bounds for the Resonance Values.

Output

For each query, print a single integer on a new line, representing the total count of Spirit-Oaks meeting the criteria.

Example
Input
7 5
1 2 1 3 2 7 2
2 5 1 2
1 4 1 1
1 6 2 3
7 7 2 2
1 7 8 10
Output
3
2
3
1
0