Pour un tableau $A[1..n]$, un sous-tableau est $A[i..j]$ avec $1 \le i \le j \le n$. La somme du sous-tableau $A[i..j]$ est $A[i]+\cdots+A[j]$. Deux tableaux d’entiers $A[1..n]$ et $B[1..m]$ sont donnés. Écrivez un programme qui compte toutes les paires composées d’un sous-tableau de $A$ et d’un sous-tableau de $B$ dont les sommes donnent ensemble $t$.

Par exemple, pour $A=(1,3,1,2)$, $B=(1,3,2)$ et $t=5$, il existe 7 paires de sous-tableaux de $A$ et $B$ de somme totale 5, comme indiqué ci-dessous.

$$ \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} $$

Entrée

La première ligne contient $t$ ($-1{,}000{,}000{,}000 \le t \le 1{,}000{,}000{,}000$).

La deuxième ligne contient la taille $n$ du tableau $A$ ($1 \le n \le 1{,}000$).

La troisième ligne contient les éléments de $A$ dans l’ordre, à partir de $A[1]$.

La quatrième ligne contient la taille $m$ du tableau $B$ ($1 \le m \le 1{,}000$).

La dernière ligne contient les éléments de $B$ dans l’ordre, à partir de $B[1]$.

Chaque élément est un entier compris entre $-1{,}000{,}000$ et $1{,}000{,}000$, bornes incluses. Les nombres sont séparés par un espace.

Sortie

Sur la première ligne, affichez le nombre de paires de sous-tableaux de $A$ et $B$ dont les sommes donnent ensemble $t$.

S’il n’existe aucune paire de sous-tableaux de somme totale $t$, affichez 0.

Exemples

Entrée 1

5
4
1 3 1 2
3
1 3 2

Sortie 1

7