F. Sequence of words
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

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.

Input

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

Output

Output Q lines, representing the answer for each query.

Examples
Input
mlcpet
2
3 3
3 4
Output
1
4
Input
yourtexthereblabla
3
6 2
4 5
2 13
Output
12
6
5