Interval Query Counting

You are given an array of n integers and q queries. Each query is represented by four integers: l, r, a and b. For each query, you need to consider the subarray from the l-th element to the r-th element (1-indexed). Your task is to find:

• The total number of elements in the subarray that satisfy \(a \le x \le b\).
• The number of distinct elements in the subarray that satisfy \(a \le x \le b\).

Input Format: The first line contains two integers n and q. The second line contains n integers representing the array. Then q lines follow, each containing four integers: l, r, a and b.

Output Format: For each query, output two space-separated integers, where the first integer is the total count and the second is the count of distinct numbers in the specified interval.

inputFormat

The input begins with a line containing two integers n and q. The next line contains n integers representing the array elements. Each of the following q lines contains four integers: l, r, a, and b.

Note: The array is 1-indexed.

outputFormat

For each query, print a single line with two integers. The first integer is the total number of elements between indices l and r (inclusive) that are between a and b (inclusive), while the second integer is the number of distinct among these elements.

sample

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

3 2
2 1
3 2