#PQJ61x355. QOJ 61_355

    ID: 3017 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SNOI 2019数论

QOJ 61_355

给出正整数 P,Q,TP, Q, T,大小为 nn 的整数集 AA 和大小为 mm 的整数集 BB,请你求出:

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

换言之,就是问有多少个小于 TT 的非负整数 xx 满足:xx 除以 PP 的余数属于 AA 且 xx 除以 QQ 的余数属于 BB。

输入格式

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

第二行 nn 个用空格隔开的整数,表示集合 A={A1,A2,…,An}A=\{A_1,A_2,\dots ,A_n\}。保证 AiA_i 两两不同,且 0≤Ai<P0 \le A_i < P。

第三行 mm 个用空格隔开的整数,表示集合 B={B1,B2,…,Bm}B=\{B_1,B_2,\dots ,B_m\}。保证 BiB_i 两两不同,且 0≤Bi<Q0 \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%10\% 的数据,T≤106T \le 10^6。

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

对于另外 10%10\% 的数据,TT 是 P,QP, Q 的公倍数。

对于另外 10%10\% 的数据,P,QP, Q 互质,且 P,Q≤105P,Q \le 10^5。

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

对于另外 10%10\% 的数据,P,Q≤105P,Q \le 10^5。

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