Problem

Given a sequence A with n elements, a sequence B with m elements, q queries each consisting of an integer c.
For each query
The absolute value of the difference between the sum of all [la, ra] in sequence A and the sum of all [lb, rb] in sequence B is c. La, ra, lb, rb (0 ≤ la ≤ ra ≤ ra ≤ Find the number of combinations of n−1, 0 ≤ lb ≤ rb ≤ m−1, sequence numbers start from 0).

Constraints

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

Input

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

All inputs are given as integers.
The number of elements n and m in the sequence and the number of queries q are given in the first row.
The elements of sequence A are given in the second row, and the elements of sequence B are given in the third row, separated by blanks.
The value ci of each query is given from the 4th line to the q line.

Output

The output consists of q lines. Print the number of combinations for each query in turn on one line.

Examples

Input

3 3 1
1 2 3
3 1 2
3

Output

6

Input

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

Output

3
4

见题面

见题面