Sum of Sequences

Problem

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

Input

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

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

Constraints

• 1 ≤ n, m ≤ 4×10⁴
• 1 ≤ q ≤ 10⁵
• 1 ≤ a_i, b_i ≤ 5
• 0 ≤ c_i ≤ 2×10⁵

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