For an array $A[1..n]$, a subarray is $A[i..j]$ with $1 \le i \le j \le n$. The sum of the subarray $A[i..j]$ is $A[i]+\cdots+A[j]$. You are given two arrays of integers, $A[1..n]$ and $B[1..m]$. Write a program that counts all pairs consisting of a subarray of $A$ and a subarray of $B$ whose sums add up to $t$.

For example, if $A=(1,3,1,2)$, $B=(1,3,2)$, and $t=5$, there are 7 pairs of subarrays of $A$ and $B$ with total sum 5, as follows.

$$ \begin{aligned} A[1]+B[1]+B[2] &= A[1]+A[2]+B[1] \\ &= A[2]+B[3] \\ &= A[2]+A[3]+B[1] \\ &= A[3]+B[1]+B[2] \\ &= A[3]+A[4]+B[3] \\ &= A[4]+B[2] = 5. \end{aligned} $$

Input

The first line contains $t$ ($-1{,}000{,}000{,}000 \le t \le 1{,}000{,}000{,}000$).

The second line contains the size $n$ of array $A$ ($1 \le n \le 1{,}000$).

The third line contains the elements of $A$ in order, starting with $A[1]$.

The fourth line contains the size $m$ of array $B$ ($1 \le m \le 1{,}000$).

The last line contains the elements of $B$ in order, starting with $B[1]$.

Each element is an integer between $-1{,}000{,}000$ and $1{,}000{,}000$, inclusive. Numbers are separated by one space.

Output

On the first line, print the number of pairs of subarrays of $A$ and $B$ whose sums add up to $t$.

If there are no such pairs with total sum $t$, print 0.

Examples

Input 1

5
4
1 3 1 2
3
1 3 2

Output 1

7