Problem Statement

Warning : The intended solution takes just under 1 second ($863$[ms]) in C++. In other languages, the same approach as the intended solution may not pass.

There are a sequence $A = {A[0], A[1], …, A[L-1]}$ of length $L$ and a sequence $B = {B[0], B[1], …, B[M-1]}$ of length $M$.
Neither of the sequences $A$, $B$ has duplicate elements. That is,
for all pairs $(i, j)$ satisfying $0 \le i < j \le L-1$, $A[i] ≠ A[j]$ holds, and
for all pairs $(i, j)$ satisfying $0 \le i < j \le M-1$, $B[i] ≠ B[j]$ holds.
In addition, every element of the sequences $A$, $B$ is an integer between $1$ and $N$, inclusive.

Here, we define "the sequence $X$ contains the value $Y$".
If one or more elements of the sequence $X$ have the value $Y$, we say that "the sequence $X$ contains the value $Y$".
If no element of the sequence $X$ has the value $Y$, we say that "the sequence $X$ does not contain the value $Y$".

Let $Bv$ be the sequence obtained by adding $v$ to all elements of the sequence $B$ (uniformly).
Find the number of integer values contained in both the sequence $A$ and the sequence $Bv$.
(Here, the range of $v$ is $0 <= v <= Q-1$.)

Input

L M N
A[0] … A[L-1]
B[0] … B[M-1]
Q

$1 \le N \le 10^5$
$1 \le L \le N$
$1 \le M \le N$
$1 \le A[i] \le N$
$1 \le B[i] \le N$
$1 \le Q \le N$

Additional constraints:
subtask1 : $N \le 3000$, $Q = 1$
subtask2 : $N \le 3000$
subtask3 : $Q = 1$
subtask4 : None

Output

The output consists of $Q$ lines.
On the $i+1$-th line ($i >= 0$), print the number of integer values contained in both the sequence $A$ and the sequence $Bi$.
Print a newline at the end.

Sample

4 2 5
1 2 3 5
1 2
5

2
2
1
1
1

11 11 32
1 4 7 10 13 16 19 22 25 28 30
1 2 4 6 8 12 16 24 27 28 29
1

4

5 6 210
1 2 5 210 15
5 4 2 7 10 3
5

2
1
1
1
0