NIO is given two strings $S$ and $T$ consisting of lowercase letters, an integer $k$ and $2k$ integers $l_i, r_i\ (1\leq i \leq k)$.

Define $U = S[l_1, r_1] + S[l_2, r_2] + \cdots + S[l_k, r_k]$. He has $q$ queries, each described by two integers $x$ and $y$. For a query, he wants to know the number of times that $T$ appears in $U[x, y]$. Help him!

• $S[l, r]$ is $S_lS_{l + 1}\cdots S_r$.

• $S + T$ is $S_1S_2\cdots S_{|S|}T_1T_2\cdots T_{|T|}$.

The first line contains a single string $S\ (1\leq |S| \leq 10 ^ 6)$.

The second line contains a single string $T\ (1\leq |T| \leq 5\times 10 ^ 5)$.

The third line contains two integers $k$ and $q\ (1\leq k, q \leq 5\times 10 ^ 5)$.

Each of the next $k$ lines contains two integers $l_i$ and $r_i\ (1\leq l_i\leq r_i \leq |S| )$.

Each of the next $q$ lines contains two integers $x_i$ and $y_i\ (1\leq x_i\leq y_i \leq |U|)$.

Print $q$ lines. The $i$-th of them contains a single integer - the answer to the $i$-th query.

$U = \texttt{abaabaabaaababaababbabaa}$