Problem E
String Hashing

Given is a string $S = s_0 s_1 ... s_{N-1}$. Your task is to compute hashes of substrings of this string.

You will be given a list of queries of the form $L, R$. For each query, you should output a hash $H(L, R)$ such that for two hashes are equal if their corresponding substrings are equal (i.e. $H(L, R) = H(L’, R’)$ if $s_ L s_{L+1} ... S_{R - 1} = s_{L'} s_{L'+1} ... S_{R' - 1}$), and different with high probability if the corresponding substrings are different.

Your hashes should be non-negative $64$-bit integers.

Input

The first line of input contains the string $S$, consisting only of letters a-z. The string will contain at least one letter and no more than $300\, 000$.

The second line contains an integer $0 \le Q \le 300\, 000$, the number of queries.

The next and final $Q$ lines contains one query each. A line will contain two space-separated integers $0 \le L < R \le N$.

Output

For each of the $Q$ queries $L, R$, output an integer: your hash $H(L, R)$.

abba
6
0 1
3 4
1 2
2 3
0 2
2 4

33
33
34
34
143
124