402360: GYM100738 F Sequence of words

Elfus has an important language exam. He reads the first task: given a text with n characters, let's consider all words of length L. The task can be reduced to sort all words lexicographically and then, write K-th word from this list. Elfus is lazy, so on the paper sheet he'll only write the beginning position of such an word. If there are multiple beginning positions such as the word that starts there will be Kth lexicographically word, you may output any of them!

Please write a program that answers Q queries like the one from above.

On the first line you get the text, as a string of n characters (1 ≤ n ≤ 10⁵) Next line contains number number Q (1 ≤ Q ≤ 10⁵). Next Q lines contain two numbers: L and K, describing a query.

Output Q lines, representing the answer for each query.

mlcpet
2
3 3
3 4

1
4

yourtexthereblabla
3
6 2
4 5
2 13

12
6
5