题目描述

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

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

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

输入格式

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

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

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

输出格式

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

4 6 3 3 14
0 1 3
2 4 5

4

提示

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

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

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

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

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

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

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

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

• 2023.11.17 添加三组 hack 数据。