Limits 5s, 512 MB

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 SS.
  • 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 SS as input and answer QQ queries. In each query, it should take an integer KK as input and find out the KK-th lexicographically smallest code name. Since only integers are allowed in Integerland, your program should print two integers LL and RR as output for each query, where LL and RR are starting and ending indices (according to 1-based indexing) of the first occurrence of the KK-th lexicographically smallest code name in the string SS. If the KK-th lexicographically smallest code name does not exist, your program should print -1.


First line of the input contains a non-empty string SS containing only lowercase English letters. The length of SS will not be more than 10610^6.

The second line of the input contains an integer QQ (1Q1051 ≤ Q ≤ 10^5) where QQ is the number of queries.

Each of the next QQ lines of the input will contain an integer KK (1K1061 ≤ K ≤ 10^6) as query.


Print QQ lines as output where ii-th line contains the answer of the ii-th query.


2 2
1 1
1 3
1 1
3 4
2 8
3 7

A sub-string of a string SS is a contiguous sequence of characters within the string SS. 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.


Login to submit.



89% Solution Ratio
solaimanopeEarliest, Nov '19
samiulsamiFastest, 0.0s
mdshadeshLightest, 132 kB
mumith_fahim99Shortest, 1801B
Toph uses cookies. By continuing you agree to our Cookie Policy.