Subsequence Sum and Maximum Query

You are given a sequence of integers and a number of queries. Each query provides two indices l and r (1-indexed), and your task is to compute two values for the sub-sequence spanning from l to r:

$$S = \sum_{i=l}^{r} a_i$$

$$M = \max_{l \leq i \leq r} a_i$$

Output the result for each query on a separate line, where the first number is the sum and the second is the maximum element found in the specified sub-sequence.

inputFormat

The input is given via standard input (stdin). The first line contains two integers n and q, representing the number of elements in the sequence and the number of queries, respectively. The second line contains n space-separated integers denoting the sequence. Each of the following q lines contains two space-separated integers l and r representing a query.

outputFormat

For each query, output two space-separated integers: the sum of the sub-sequence from index l to r and the maximum element in that sub-sequence. Each query result should be printed on a new line via standard output (stdout).## sample

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

6 3
14 5
3 3