Bob has written a string consisting of lowercase English letters, and he is going to play a game with his 3-year-old sister Alice with the string. From now on, we denote as the length of , as the -th character of , and as the substring obtained by concatenating all the characters between the -th and -th character of (that is, ). Note that in this problem all strings are 1-indexed.

The game will last for rounds. In each round, both of the players need to choose a non-empty substring of . The player with lexicographically larger string wins the game. If two player chooses the same string, it is considered a draw. Here, for two strings and , we say is lexicographically larger than if is a prefix of and , or there exists some non-negative integer such that and for each there holds .

Bob has already know the substring Alice will choose for each round. It is easy for him to win the game, but Alice will be really sad if Bob wins too much. Therefore, Bob wants to choose the lexicographically smallest substring of that can help him win the game. For each round, help Bob figure out which string he should choose, or determine it is impossible to win.

The first line of input contains a string , denoting the string that Bob writes. It is guaranteed that  only contains lowercase English letters.

The second line contains a single integer , denoting the number of rounds.

The -th of the next  lines contains two integers , describing the -th round in which Alice chooses  as her substring.

Print a line for each round, indicating the string that Bob should choose. As the output may be too large if we require you to print the whole string, we only ask you to print the length and the ending character of the string. For example, if Bob's optimal string is , just print a line of . If Bob is impossible to win just print a single line of .

aaaabb
10
2 4
2 5
3 4
3 5
5 5
1 6
3 6
4 6
5 6
6 6

4 a
5 b
3 a
4 b
2 b
4 b
2 b
1 b
0
2 b

In the sample above, the answer strings are respectively . Note that for the -th query the string Alice chooses, , is the lexicographically largest substring of , resulting in Bob having no chance to win.