SHOCCUR - Most Occurrence

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

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

hide comments
2023-02-13 22:30:36 Simes
An assert fails showing the string is NOT of the specified length. Bad input data.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.