Minimum Number and Frequency

You are given an array of n positive integers and q queries. Each query asks for the minimum number in a given subarray and the number of occurrences of that minimum value within the subarray. Write a program to efficiently process these queries.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 100 000), separated by a space, representing the size of the array and the number of queries, respectively.

The next line contains n integers (), separated by spaces, representing the elements of the array.
The following q lines represent the queries. Each query consists of two integers l and r, separated by a space, representing the left and right indices of the subarray.

Output

For each query, print two integers separated by a space: the minimum number in the subarray and the number of occurrences of that minimum value within the subarray.

Examples