include <bits/stdc++.h>

define ull unsigned long long

using namespace std; ull gcd(ull a, ull b){ if(b == 0) return a; return gcd(b, a%b); } ull lcm(ull a, ull b){ if(double(a)*b/gcd(a, b) > pow(10, 18)){ return -1; } return b/gcd(a, b)*a; } int main() { ull a, b, k, m, x, c, q, say, LCM = 1, L; cin>>a>>b; cin>>k>>m; for(int i = 0; i < k; i++){ cin>>x; LCM = lcm(LCM, x); if(LCM == -1){ cout<<"0\n"; return 0; } } ull y[m]; for(int i = 0; i < m; i++){ cin>>y[i]; } ull cavab1 = (a - 1)/LCM; ull cavab2 = b/LCM; for(int i = 1; i < (1<<m); i++){ c = i; say = 0; L = LCM; for(int j = 0; j < m; j++){ q = c%2; if(q == 1){ say++; L = lcm(L, y[j]); if(L == -1){ L = b + 1; break; } } c = c/2; } if(say%2 == 1){ cavab1 -= (a - 1)/L; cavab2 -= b/L; } else{ cavab1 += (a - 1)/L; cavab2 += b/L; } } cout<<cavab2 - cavab1<<endl; }