Most Frequent Character in Substrings

You are given a string S and an integer Q representing the number of queries. Each query consists of two integers L and R (1-indexed) which define a substring of S.

For each query, your task is to find the most frequently occurring character in the substring S[L:R]. In the case where more than one character has the maximum frequency, choose the lexicographically smallest character.

Formally, for a query with indices L and R, if we denote by \(freq(c, S[L..R])\) the number of occurrences of character \(c\) in the substring and \(M = \max_{d}freq(d, S[L..R])\), then you must output \[ \min\{ c \mid freq(c, S[L..R]) = M \}\]

inputFormat

The input is read from stdin and has the following format:

S
Q
L1 R1
L2 R2
... 
LQ RQ

Where:

• S is a non-empty string.
• Q is the number of queries.
• Each of the next Q lines contains two integers L and R (1-indexed) representing a query.

outputFormat

For each query, output the most frequent character on a new line to stdout. In case of ties, output the lexicographically smallest character.

## sample

abracadabra
3
1 3
2 9
5 10

a
a
a

</p>