[AdditionalFile3096.zip](file://AdditionalFile3096.zip?type=additional_file)

#3096. 「SNOI2019」数论

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

给出正整数 $P, Q, T$，大小为 $n$ 的整数集 $A$ 和大小为 $m$ 的整数集 $B$，请你求出：

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

换言之，就是问有多少个小于 $T$ 的非负整数 $x$ 满足：$x$ 除以 $P$ 的余数属于 $A$ 且 $x$ 除以 $Q$ 的余数属于 $B$。

输入格式

第一行 $5$ 个用空格隔开的整数 $P,Q,n,m,T$。

第二行 $n$ 个用空格隔开的整数，表示集合 $A=\{A_1,A_2,\dots ,A_n\}$。保证 $A_i$ 两两不同，且 $0 \le A_i < P$。

第三行 $m$ 个用空格隔开的整数，表示集合 $B=\{B_1,B_2,\dots ,B_m\}$。保证 $B_i$ 两两不同，且 $0 \le B_i < Q$。

输出格式

输出一行一个整数表示答案。

样例

输入

4 6 3 3 14
0 1 3
2 4 5

输出

4

数据范围与提示

对于所有数据，$1 \le n, m \le 10^6, 1 \le P, Q \le 10^6, 1 \le T \le 10^{18}$。

• 对于 $10\%$ 的数据，$T \le 10^6$。

• 对于另外 $20\%$ 的数据，$P, Q \le 1000$。

• 对于另外 $10\%$ 的数据，$T$ 是 $P, Q$ 的公倍数。

• 对于另外 $10\%$ 的数据，$P, Q$ 互质，且 $P,Q \le 10^5$。

• 对于另外 $10\%$ 的数据，$P, Q$ 互质。

• 对于另外 $10\%$ 的数据，$P,Q \le 10^5$。

• 对于余下 $30\%$ 的数据，无特殊限制。