Sum of Sequences

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

inputFormat

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.

outputFormat

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

样例

3 3 1
1 2 3
3 1 2
3

6