Lexicographically Smallest Substring Queries

You are given a string s and Q queries. Each query consists of two integers l and r, representing a 1-indexed range in the string. For each query, your task is to extract the substring s[l...r] and find the lexicographically smallest non-empty substring (i.e. the one that comes first in alphabetical order) among all possible substrings of s[l...r].

More formally, for a given substring P = s[l...r], consider all substrings P[i..j] where 1 ≤ i ≤ j ≤ |P|. Among these, you need to find and return the substring X such that for any other substring Y it holds that X < Y in lexicographical order. This can be mathematically written as:

$$X = \min\{P[i..j] : 1 \le i \le j \le |P|\}$$

The queries are independent so that the output for each query should be printed in a separate line.

inputFormat

The first line contains the string s consisting of lowercase English letters.

The second line contains an integer Q representing the number of queries.

The next Q lines each contain two integers l and r (1 ≤ l ≤ r ≤ |s|), indicating the range for that query.

outputFormat

For each query, output the lexicographically smallest substring found in that range on a separate line.

## sample

abacaba
3
1 3
2 5
1 7

a
a
a

</p>