Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Story of Stringland

By SMAN2901 · 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 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.

Input

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.

Output

Print Q lines as output where i‘th line contains the answer of the i‘th query.

Samples

InputOutput
bab
4
1
2
3
4
2 2
1 1
1 3
-1
InputOutput
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.


Discussion
Statistics

100% Solution Ratio

solaimanopeEarliest, 1w ago

ShahinFastest, 0.6s

AungkurLightest, 136 MB

kzvd4729Shortest, 1890B

Submit

Login to submit