Consider an input string of length less than 1000. For example, " abcdefgabcdefg".
We may denote a substring of this input string by a pair of indexes. For example, the pair (5, 9) represents the substring "fgabc". (The index starts from 0, following the C convention.)
Now, given N pairs of the indexes representing N substrings, we are interested in sorting these substrings in alphabetical order. For example, if the five pairs are (8, 12), (7, 11), (6, 10), (4, 8), and (5, 9), then the corresponding substrings are "bcdef", "abcde", "gabcd", "efgab", "fgabc". The output of the sorted substrings would be
abcde
bcdef
efgab
fgabc
gabcd
The first line contains an input string. The length of the input string is less than 1000.
The second line is an integer N indicating the number of substrings, where N<=100.
The next N lines are the N pairs of indexes denoting the N substrings. (The index of the first character in the input string is 0 as in the C array indexing convention.)
The output contains N lines for the N sorted substrings. Each line should be ended with a newline character ' '.