Problem B
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^{\prime },R^{\prime })$ if $s_L{s}_{L+1}...S_{R-1}=s_{L^{\prime }}{s}_{L^{\prime }+1}...S_{R^{\prime }-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 $300000$.

The second line contains an integer $0\le Q\le 300000$, 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