Submit
 

K : Sum of Sequences

Time Limit : 2 sec, Memory Limit : 524288 KB

Problem K: Sum of Sequences

Problem

n個の要素を持つ数列Am個の要素を持つ数列Bそれぞれが整数la,ra,lb,rbからなるq個のクエリが与えられる。 それぞれが整数cからなるq個のクエリが与えられる。
各クエリについて、
数列Aの[la,ra]を全て足した数と数列Bの[lb,rb]を全て足した数の差の絶対値がcになるla,ra,lb,rb (0 ≤ laran−1, 0 ≤ lbrbm−1, 配列の番号は0番から始まる) の組み合わせの数を求めよ。

Input

n m q
a0 a1 ... an−1
b0 b1 ... bm−1
c0
c1
...
cq−1

入力は全て整数で与えられる。
1行目にnmとクエリ数qが与えられる。
2行目に数列Aの要素、3行目に数列Bの要素が空白区切りで与えられる。
4行目からq行に各クエリのciが与えられる。

Constraints

入力は以下の条件を満たす。

  • 1 ≤ n, m ≤ 4×104
  • 1 ≤ q ≤ 105
  • 1 ≤ ai, bi ≤ 5
  • 0 ≤ ci ≤ 2×105

Output

q行に各クエリの組み合わせの数を出力せよ。

Sample Input 1

3 3 1
1 2 3
3 1 2
3

Sample Output 1

6

Sample Input 2

5 4 2
1 2 3 4 5
2 2 2 2
11
12

Sample Output 2

3
4