Description

It is already 2 a.m. After finishing some Codeforces problems, Xiao A pulled out the English test paper. The English homework is not much; it takes exactly one hour to finish. Then there is math homework that also takes one hour, followed by chemistry, physics, Chinese, and so on, each of which also takes one hour. Xiao A feels enormous pressure.

At this moment, Xiao A ran into a very nasty math problem: given a sequence of length $n$ and several queries, each query is on an interval of the sequence (from the $l$-th number to the $r$-th number). First, you need to count how many numbers in this interval are greater than or equal to $a$ and less than or equal to $b$. Second, you need to count how many distinct values are greater than or equal to $a$ and less than or equal to $b$ and appear in this interval.

Facing testdata of tens of thousands in scale, Xiao A is almost desperate and can only ask you, the expert, for help. Please help him.

Input Format

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

The next $n$ positive integers, each not exceeding $10^5$, form the sequence.

Then there are $m$ lines. Each line contains four integers $l, r, a, b$; see the statement for their meanings.

Output Format

Output $m$ lines, one for each query. For each query, output two numbers: the number of elements in the interval $[l, r]$ whose values lie in $[a, b]$, and the number of distinct values that are greater than or equal to $a$ and less than or equal to $b$ and appear in this interval (see the sample).

3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3

2 2
1 1
3 2
2 1

Hint

$N \le 100000, M \le 100000$. All read numbers are positive integers in $[1, 10^5]$.

Translated by ChatGPT 5