XCorr

There are two sequences of equal length, $X=(x_0, x_1, \cdots, x_{n-1})$ and $Y=(y_0, y_1, \cdots, y_{n-1})$.

Each element of the two sequences is a nonnegative integer. The following is an example with $n=5$.

$X=(1,0,0,0,1)$

$Y=(0,5,2,0,1)$

For any integer $t$, $XCorr(t)$ is defined as follows.

$XCorr(t)=\displaystyle\sum_{i=0}^{n-1}{x_iy_{i+t}}$

(If $i<0$ or $i\geq n$, we take $x_i=y_i=0$.)

For example, when $t$ is $0, 1, -1$, the value of $XCorr(t)$ is computed as follows.

$XCorr(0) = x_0y_0 + x_1y_1 + \dots + x_{n-1}y_{n-1}$

$XCorr(1) = x_0y_1 + x_1y_2 + \dots + x_{n-1}y_n$

Cells in gray do not affect the result. $y_0$ is not included in the expression, and $x_{n-1}$ is multiplied by $y_n=0$, so it does not affect the result. Therefore, for the example sequences $X$ and $Y$, $XCorr(1)$ is computed as follows.

$1\times5+0\times2+0\times0+0\times1=5$

$XCorr(-1) = x_0y_{-1} + x_1y_0 + \dots + x_{n-1}y_{n-2}$

For any range of $t$ values $(a \le t \le b)$, the sum of all $XCorr(t)$, written $S(a,b)$, is defined as follows.

$S(a,b)=\displaystyle\sum_{a \le t \le b}{XCorr(t)}$

Given the sequences $X$, $Y$ and the range endpoints $a$, $b$ for $t$, write a program that computes $S(a,b)$.

The standard input gives the following information. The first line gives $N$, the number of nonzero integers in sequence $X$. (This is not the length $n$ of the sequence.) The next $N$ lines give, for each positive integer $x_i$ of sequence $X$, its index $i$ and the value $x_i$, in increasing order of index. From the next line onward, sequence $Y$ is given in the same way as $X$. ($M$, the number of nonzero integers in $Y$, is given, and the next $M$ lines give, for each positive integer $y_i$ of sequence $Y$, its index $i$ and the value $y_i$, in increasing order of index.) The next line gives the integer $a$, the minimum of the range of $t$, and the line after that gives the integer $b$ ($a \le b$), the maximum of the range of $t$.

Print the value of $S(a,b)=\displaystyle\sum_{a \leq t \leq b}{XCorr(t)}$ to standard output as an integer.

In every subtask, the input values $x_i, y_i$ satisfy $1 \leq x_i, y_i \leq 3,000$.