The Story of Stringland
The king of Stringland is employing an elite force of undercover agents to protect the kingdom from the attack of Integerland. The king has decided to give each of these agents a code name. These code names will be chosen according to the following rules:
- Each agent’s code name must be a non-empty sub-string of the string S.
- Each agent’s code name must be a palindrome.
- Code names of any two agents can’t be the same.
Since the number of possible code names is limited, the king has ensured that the number of agents is equal to the number of possible code names. These agents will operate secretly in Integerland. They can’t directly use their code names because strings are not allowed in Integerland. They will communicate with each other using the lexicographical order of their code names. For example, if there are three agents with code names a, b and aba, then a will be called 1 because it’s the lexicographically smallest code name, aba will be called 2 because it’s the lexicographically second-smallest code name and b will be called 3 because it’s the lexicographically third-smallest code name.
But it’s very difficult for them to remember the ordering of code names of all the agents. Since you are the royal programmer of Stringland, the king has given you the responsibility to solve this problem.
Your task is to write a program that will take the string S as input and answer Q queries. In each query, it should take an integer K as input and find out the K‘th lexicographically smallest code name. Since only integers are allowed in Integerland, your program should print two integers L and R as output for each query, where L and R are starting and ending indices (according to 1-based indexing) of the first occurrence of the K‘th lexicographically smallest code name in the string S. If the K‘th lexicographically smallest code name does not exist, your program should print -1.
First line of the input contains a non-empty string S containing only lowercase English letters. The length of S will not be more than 106.
The second line of the input contains an integer Q (1 ≤ Q ≤ 105) where Q is the number of queries.
Each of the next Q lines of the input will contain an integer K (1 ≤ K ≤ 106) as query.
Print Q lines as output where i‘th line contains the answer of the i‘th query.
bab 4 1 2 3 4
2 2 1 1 1 3 -1
aabbcbbacc 5 1 5 10 3 6
1 1 3 4 -1 2 8 3 7
A sub-string of a string S is a contiguous sequence of characters within the string S. For example, a, b, ab, ba, bab are sub-strings of the string bab, but aa, bb, c are not.
A palindrome is a sequence of characters which reads the same backward as forward. For example, a, b, aa, aba are palindromes, but ab, ba, abb, baa are not.