Plant Classification

Nathan is a botanist who is studying a collection of plants with varying heights. Given a list of plant heights and several queries, each specifying a range by indices, your task is to determine the tallest and the shortest plants in that specific range. Formally, for a given list (H = [h_0, h_1, \dots, h_{n-1}]) and a query range ([a, b]) (where (0 \leq a \leq b < n)), you are to compute (\max{h_a, h_{a+1}, \dots, h_b}) and (\min{h_a, h_{a+1}, \dots, h_b}).

Example:
For (H = [4, 7, 2, 9, 5, 1, 3]) and queries ((1, 4)), ((0, 6)), and ((2, 5)), the answers would be ((9, 2)), ((9, 1)), and ((9, 1)), respectively.

inputFormat

The input is given from standard input (stdin) in the following format:

n q h0 h1 h2 ... h(n-1) a1 b1 a2 b2 ... aq bq

Where:
• (n) is the number of plants.
• (q) is the number of queries.
• The second line contains (n) integers representing the heights of the plants.
• Each of the following (q) lines contains two integers (a) and (b) (0-indexed) representing a query range.

outputFormat

For each query, output a line with two space-separated integers: the first is the maximum height and the second is the minimum height in the given range, printed to standard output (stdout).## sample

7 3
4 7 2 9 5 1 3
1 4
0 6
2 5

9 2
9 1
9 1