SHOCCUR - Most Occurrence

no tags 

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 ≤ 105, 1 ≤ q ≤ 105), 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

hide comments
Simes: 2023-02-13 22:30:36

An assert fails showing the string is NOT of the specified length. Bad input data.


Added by:Mozahid
Date:2019-09-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All