問題文

Warning : 想定解法の実行時間はC++で1秒弱($863$[ms])です。他の言語の場合、想定解法と同じ方法では通らない可能性があります。

長さ$L$の数列$A = {A[0], A[1], …, A[L-1]}$、長さ$M$の数列$B = {B[0], B[1], …, B[M-1]}$がある。
数列$A$, $B$はそれぞれ、重複する要素がない数列である。すなわち、
$0 \le i < j \le L-1$を満たす全ての$(i, j)$組について、$A[i] ≠ A[j]$が成り立ち、
$0 \le i < j \le M-1$を満たす全ての$(i, j)$組について、$B[i] ≠ B[j]$が成り立つ。
また、数列$A$,$B$のどの要素も$1$以上$N$以下の整数である。

ここで、「数列$X$に値$Y$が含まれる」を定義する。
数列$X$の要素の内、一つ以上の要素の値が$Y$であるとき、「数列$X$に値$Y$が含まれる」と定義する。
数列$X$のどの要素の値も$Y$でない場合、「数列$X$に値$Y$が含まれない」と定義する。

数列$B$の全ての要素に(一様に)$v$を加算した数列を$Bv$としたとき、
数列$A$にも数列$Bv$にも含まれるような整数値はいくつあるか求めよ。
(ただし$v$の変域は、$0 <= v <= Q-1$とする。)

入力

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$

追加制約：
subtask1 : $N \le 3000$, $Q = 1$
subtask2 : $N \le 3000$
subtask3 : $Q = 1$
subtask4 : 無し

出力

出力は$Q$行から成る。
$i+1$行目($i >= 0$)に、数列$A$にも数列$Bi$にも含まれるような整数値の数を出力せよ。
最後に改行してください。

サンプル

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