Count Numbers with Specified Modular Remainders

You are given positive integers ( P ), ( Q ), and ( T ), along with two sets of integers: a set ( A ) of size ( n ) and a set ( B ) of size ( m ). Your task is to compute [ \sum_{x=0}^{T-1} \mathbf{1}{(x \bmod P) \in A \land (x \bmod Q) \in B}, ] which is equivalent to counting the number of non-negative integers ( x < T ) such that the remainder when ( x ) is divided by ( P ) belongs to ( A ) and the remainder when ( x ) is divided by ( Q ) belongs to ( B ).

Note that the sequence of remainders repeats with period ( \mathrm{lcm}(P,Q) ). You may use this fact to optimize your solution if ( T ) is large.

inputFormat

The input consists of three lines:

1. The first line contains three integers: ( P ), ( Q ), and ( T ).
2. The second line starts with an integer ( n ) followed by ( n ) space-separated integers denoting the elements of set ( A ).
3. The third line starts with an integer ( m ) followed by ( m ) space-separated integers denoting the elements of set ( B ).

outputFormat

Output a single integer: the number of non-negative integers ( x < T ) that satisfy the condition that ( x \bmod P ) belongs to ( A ) and ( x \bmod Q ) belongs to ( B ).

sample

3 4 10
2 0 1
3 1 2 3

5