题目描述
给出正整数 P,Q,T,大小为 n 的整数集 A 和大小为 m 的整数集 B,请你求出:
i=0∑T−1[(i∈A(modP))∧(i∈B(modQ))]
换言之,就是问有多少个小于 T 的非负整数 x 满足:x 除以 P 的余数属于 A 且 x 除以 Q 的余数属于 B。
输入格式
第一行 5 个用空格隔开的整数 P,Q,n,m,T。
第二行 n 个用空格隔开的整数,表示集合 A={A1,A2,…,An}。保证 Ai 两两不同,且 0≤Ai<P。
第三行 m 个用空格隔开的整数,表示集合 B={B1,B2,…,Bm}。保证 Bi 两两不同,且 0≤Bi<Q。
输出格式
输出一行一个整数表示答案。
样例
4 6 3 3 14
0 1 3
2 4 5
4
见附加文件。
数据范围与提示
对于所有数据,1≤n,m≤106,1≤P,Q≤106,1≤T≤1018。
-
对于 10% 的数据,T≤106。
-
对于另外 20% 的数据,P,Q≤1000。
-
对于另外 10% 的数据,T 是 P,Q 的公倍数。
-
对于另外 10% 的数据,P,Q 互质,且 P,Q≤105。
-
对于另外 10% 的数据,P,Q 互质。
-
对于另外 10% 的数据,P,Q≤105。
-
对于余下 30% 的数据,无特殊限制。