Most Frequent Character in a Substring

Given a string \( s \) and \( Q \) queries, each query consists of two integers \( l \) and \( r \). For each query, extract the substring \( s[l-1:r] \) (both endpoints inclusive) and find the most frequent character. If there are multiple characters with the same highest frequency, output the lexicographically smallest one.

For example, if \( s = "abcabcbb" \) and the queries are \( (1,3) \), \( (2,5) \), and \( (1,8) \), the outputs are \( 'a', 'b', 'b' \) respectively.

inputFormat

The input is read from standard input. 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 space-separated integers \( l \) and \( r \), representing the 1-indexed start and end positions of the substring.

outputFormat

For each query, print the most frequent character in the substring \( s[l-1:r] \) on a separate line. If multiple characters have the same maximum frequency, print the lexicographically smallest one.

abcabcbb
3
1 3
2 5
1 8

a
b
b