Given a string S of length n and q queries. In each query, You have to find out which character occur most of the time in a given range (L, R). If there are several answers, you have to find out the lexicographically smallest letter.

Input

The first line will contain two integers n, q (1 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵), the length of the string and the number of queries respectively. The next line contains the string S.

Next q lines will contain two integers L and R.

Output

For each query, find out the most occurring character and the occurrence count. If there are several answers, you have to find out the lexicographically smallest character.

Example

Input
13 5
abbacccdefgha
1 13
1 10
3 6
11 12
8 12

Output
a 3
c 3
c 2
g 1
d 1