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.

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$.

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

Sample Input 1 | Sample Output 1 |
---|---|

abba 6 0 1 3 4 1 2 2 3 0 2 2 4 |
33 33 34 34 143 124 |