Most Frequent Character in Substring

Given a string s consisting solely of lowercase letters and several queries, each query specifies a range [start, end]. For each query, determine the most frequent character in the substring s[start..end] (inclusive). If there is more than one character with the highest frequency, output the lexicographically smallest one. Formally, if the frequency counts are given by \(f(c)\) for each character \(c\) in the substring, then the answer for the query is \(\min\{ c : f(c)=\max_{d} f(d) \}\).

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains the string s.
• The second line contains an integer q representing the number of queries.
• Each of the next q lines contains two integers start and end (0-indexed) separated by a space.

outputFormat

Output the answer for each query as the most frequent character. The answers should be printed in order and separated by a single space.

abacabad
1
0 3

a