408994: GYM103409 J Suffix Automaton

JB is the National Olympiad Tutor of Suffix Automaton. Today he comes up with the following problem.

Suppose you have a string $$$S$$$, we write down all the distinct substrings in $$$S$$$. Then we sort the strings according to their length in increasing order. For two strings with the same length, the one that has the smaller lexicographical order comes first. Now we have a sorted string sequence $$$A$$$.

JB has $$$Q$$$ questions, for each question, he will give you one integer $$$k$$$ and suppose you to tell him the $$$k$$$-th string in $$$A$$$.

To simplify the problem, you just need to tell him the left and right positions in $$$S$$$ of the first occurrence of the string.

The first line contains one string $$$S$$$ ($$$1\leq |S|\leq 10^6$$$), containing only lowercase letters.

The second line contains one integer $$$Q$$$ ($$$1\leq Q\leq 10^6$$$).

The following $$$Q$$$ lines describe the questions, each of which contains one integer $$$k$$$ ($$$1\leq k\leq 10^{12}$$$).

For each question, print two integers $$$l, r$$$, denoting the left and right positions in $$$S$$$ of the first occurrence of the answer string. If $$$k$$$ is greater than the length of $$$A$$$, just print "-1 -1".

ccpcguilin
5
1
10
4
8
26

1 1
2 3
8 8
1 2
4 7

banana
3
5
10
16

1 2
2 5
-1 -1