Description

Given positive integers $P, Q, T$, an integer set $A$ of size $n$, and an integer set $B$ of size $m$, please compute:

$$\sum_{i=0}^{T-1}[(i\bmod P) \in A \land (i\bmod Q) \in B]$$

In other words, ask how many non-negative integers $x$ less than $T$ satisfy: the remainder of $x$ divided by $P$ belongs to $A$, and the remainder of $x$ divided by $Q$ belongs to $B$.

Input Format

The first line contains $5$ integers separated by spaces: $P, Q, n, m, T$.

The second line contains $n$ integers separated by spaces, representing the set $A=\{A_1,A_2,\cdots,A_n\}$. It is guaranteed that all $A_i$ are pairwise distinct, and $0 \leq A_i < P$.

The third line contains $m$ integers separated by spaces, representing the set $B=\{B_1,B_2,\cdots,B_m\}$. It is guaranteed that all $B_i$ are pairwise distinct, and $0 \leq B_i < Q$.

Output Format

Output one integer on a single line, denoting the answer.

4 6 3 3 14
0 1 3
2 4 5

4

Hint

For all testdata, $1 \leq n,m \leq 10^6$, $1 \leq P,Q \leq 10^6$, and $1 \leq T \leq 10^{18}$.

For $10\%$ of the testdata, $T \leq 10^6$.

For another $20\%$ of the testdata, $P,Q \leq 1000$.

For another $10\%$ of the testdata, $T$ is a common multiple of $P$ and $Q$.

For another $10\%$ of the testdata, $P$ and $Q$ are coprime, and $P,Q \leq 10^5$.

For another $10\%$ of the testdata, $P$ and $Q$ are coprime.

For another $10\%$ of the testdata, $P,Q \leq 10^5$.

For the remaining $30\%$ of the testdata, there are no special constraints.

• 2023.11.17 Added three groups of hack testdata.

Translated by ChatGPT 5