Subarray Sum and Maximum Frequency Query

Alice is given an array of integers. She also receives a series of queries, each asking for two specific pieces of information about a subarray defined by a range [l, r] (1-indexed):

• The sum of all elements in the subarray, i.e., \( S = \sum_{i=l}^{r} a_i \).
• The maximum frequency of any integer within the subarray.

Your task is to process each query and output these two values. This problem can be efficiently solved by computing a prefix sum array for the summations and counting frequencies for each query range.

Note: The indices are 1-indexed.

inputFormat

The first line of input contains two integers n and q, where n denotes the size of the array and q is the number of queries. The second line contains n space-separated integers representing the array elements. Each of the next q lines contains two integers, l and r, representing the query range (1-indexed).

outputFormat

For each query, print a line containing two space-separated integers: the sum of the subarray from index l to r and the maximum frequency count of any element within that subarray.

## sample

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

5 2
8 2
9 2

</p>