Para un arreglo $A[1..n]$, un subarreglo es $A[i..j]$ con $1 \le i \le j \le n$. La suma del subarreglo $A[i..j]$ es $A[i]+\cdots+A[j]$. Se dan dos arreglos de enteros, $A[1..n]$ y $B[1..m]$. Escribe un programa que cuente todos los pares formados por un subarreglo de $A$ y un subarreglo de $B$ cuyas sumas sumen $t$.
Por ejemplo, si $A=(1,3,1,2)$, $B=(1,3,2)$ y $t=5$, hay 7 pares de subarreglos de $A$ y $B$ con suma total 5, como se muestra a continuación.
$$ \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} $$
Entrada
La primera línea contiene $t$ ($-1{,}000{,}000{,}000 \le t \le 1{,}000{,}000{,}000$).
La segunda línea contiene el tamaño $n$ del arreglo $A$ ($1 \le n \le 1{,}000$).
La tercera línea contiene los elementos de $A$ en orden, empezando por $A[1]$.
La cuarta línea contiene el tamaño $m$ del arreglo $B$ ($1 \le m \le 1{,}000$).
La última línea contiene los elementos de $B$ en orden, empezando por $B[1]$.
Cada elemento es un entero entre $-1{,}000{,}000$ y $1{,}000{,}000$, ambos incluidos. Los números están separados por un espacio.
Salida
En la primera línea, imprime el número de pares de subarreglos de $A$ y $B$ cuyas sumas sumen $t$.
Si no hay pares de subarreglos con suma total $t$, imprime 0.
Ejemplos
Entrada 1
5 4 1 3 1 2 3 1 3 2
Salida 1
7