Most Frequent Character Query

You are given a string \( S \) and \( Q \) queries. Each query is represented by two integers \( L \) and \( R \) that denote the starting and ending indices of a substring of \( S \). Your task is to determine the most frequent character in the substring \( S[L \ldots R] \). If there is a tie (i.e. multiple characters have the same maximum frequency), you must output the lexicographically smallest character among them.

Input Format:

• The first line contains the string \( S \).
• The second line contains an integer \( Q \), the number of queries.
• Each of the next \( Q \) lines contains two integers \( L \) and \( R \) (0-indexed) separated by a space.

Output Format:

• For each query, print the most frequent character in the corresponding substring on a new line.

Constraints:

• \( 1 \leq |S| \leq 10^5 \)
• \( 1 \leq Q \leq 10^5 \)
• \( 0 \leq L \leq R \lt |S| \)

Example:

abacaba
3
1 3
0 6
2 5

a
a
a

inputFormat

The input is read from standard input and has the following structure:

• The first line contains the string \( S \).
• The second line contains an integer \( Q \), the number of queries.
• Each subsequent line contains two integers \( L \) and \( R \) separated by a space, representing a query.

outputFormat

For each query, output the most frequent character in the substring \( S[L \ldots R] \). Each result should be printed on a new line. In the case where multiple characters have the same frequency, output the lexicographically smallest one.

## sample

abacaba
3
1 3
0 6
2 5

a
a
a

</p>