题目背景

在字母王国里，每一位字母勇士都有自己的 ASCII 战力值，战力值越大，实力就越强。国王将 $n$ 位勇士排成一列，依次编号为 $1 \sim n$。每逢战前，他都需要快速了解某一段队列中，战力最强的勇士是哪一位，以便任命先锋。然而勇士数量众多，国王的询问又十分频繁，你能帮他快速回答吗？

题目描述

给定一个长度为 $n$ 且仅包含小写字母的字符串 $S$，第 $i$ 位字母勇士的 ASCII 战力就是 $S_i$ 的 ASCII 码。
有 $q$ 次询问，每次询问给出两个整数 $l, r$（$1 \le l \le r \le n$），你需要回答区间 $[l, r]$ 内 ASCII 码最大的字符，也就是这段队伍里战力最强的字母勇士。

输入格式

第一行一个字符串 $S$，仅由小写字母组成，表示勇士队列。
第二行一个整数 $q$，表示国王的询问次数。
接下来 $q$ 行，每行两个整数 $l, r$，表示一次询问的区间。

输出格式

对每个询问输出一行一个字符，表示对应区间内 ASCII 战力最大的字母勇士。

样例

abedcfg
4
1 3
2 5
4 6
3 7

e
e
f
g

样例解释

• 询问 $[1,3]$：队列 a b e，战力最高为 e（ASCII 101）。
• 询问 $[2,5]$：队列 b e d c，战力最高为 e。
• 询问 $[4,6]$：队列 d c f，战力最高为 f。
• 询问 $[3,7]$：队列 e d c f g，战力最高为 g。

数据范围与提示

• 对于 $60\%$ 的数据：$1 \le n \le 10^4$，$1 \le q \le 10^4$。
• 对于 $100\%$ 的数据：$1 \le n \le 10^5$，$1 \le q \le 10^5$，$1 \le l \le r \le n$。
• 字符串仅由小写字母构成。