// Knapsack DP is harder than FFT.
#pragma GCC optimize("Ofast")
#include<unistd.h>
const int BUF_SIZE = 2e5 + 225;
char OB[BUF_SIZE]; int OP;
inline char RC(){static char buf[BUF_SIZE],*p=buf,*q=buf;return p==q&&(q=(p=buf)+read(0,buf,BUF_SIZE))==buf?-1:*p++;}
inline int R(){static char c;int a;while((c=RC())<'0');a=c^'0';while((c=RC())>='0')a*=10,a+=c^'0';return a;}
inline long long RL(){static char c;long long a;while((c=RC())<'0');a=c^'0';while((c=RC())>='0')a*=10,a+=c^'0';return a;}
inline void W(long long n){static char buf[20],p;if(n==0)OB[OP++]='0';p=0;while(n)buf[p++]='0'+(n%10),n/=10;for(--p;p>=0;--p)OB[OP++]=buf[p];OB[OP++]='\n';if(OP>BUF_SIZE-20)write(1,OB,OP),OP=0;}

#include <algorithm>
#include <vector>
#include <queue>
#define ll long long
#define pii pair<int, ll>
#define ff first
#define ss second
#define maxn 500005
#define jizz 7122 + 1
#define mod 1000000007
using namespace std;
const ll inf = 1LL<<60;
ll a[jizz];
bool done[jizz];
ll edge[jizz], mind[jizz], pref[jizz], ans[maxn];
vector<pii> que[jizz];

int x;
int main() {
    int n, m;
    n = R(), m = R();
    for(int i = 0; i < n; ++i) a[i] = R();
    sort(a, a + n);
    x = a[0];
    for(int i = 0; i < x; ++i) edge[i] = inf, mind[i] = inf;
    for(int i = 0; i < n; ++i){
        edge[a[i] % x] = min(edge[a[i] % x], a[i]);
    }
    ll b;
    for(int i = 0; i < m; ++i){
        b = R();
        edge[b % x] = min(edge[b % x], b);
    }
    //for (int i = 0;i < x;i++) cout << edge[i] << endl;
    mind[0] = 0;
    for (int i = 0;i < x;i++) {
        ll mi = inf, ind = 0;
        for (int j = 0;j < x;j++) {
            if (!done[j] && mind[j] < mi) {
                mi = mind[j];
                ind = j;
            }
        }
        done[ind] = true;
        for (int j = 0;j < x;j++){
            mind[j] = min(
                mind[j],
                mind[ind] + edge[j - ind < 0 ? j - ind + x : j - ind]
            );
        }
    }
    sort(mind, mind + x);
    //for (int i = 0;i < x;i++) cout << mind[i] << endl;
    int q = R();
    ll l, r;
    for (int i = 1;i <= q;i++) {
        l = RL(); r = RL() + 1;
        que[r % x].emplace_back( i, r);
        que[l % x].emplace_back(-i, l);
    }
    for (int i = 0;i < x;i++) {
        for (int j = 0;j < x;j++) {
            pref[j] = (j ? pref[j - 1] : 0) + (i - mind[j] < 0 ? (i - mind[j]) / x : (i - mind[j] + x - 1) / x);
            //cout << pref[j] << " ";
        }
        //cout << endl;
        for (pii &&j: que[i]) {
            int ind = lower_bound(mind, mind + x, j.ss) - mind;
            //cout << j.ff << " " << ind << endl;
            if (j.ff > 0) {
                ans[j.ff] += ind * (j.ss / x) + (ind ? pref[ind - 1] : 0);
                //cout << j.ff << " " << ind << " " << ind * (j.ss / x) + (ind ? pref[ind - 1] : 0) << endl;
            } else {
                ans[-j.ff] -= ind * (j.ss / x) + (ind ? pref[ind - 1] : 0);
            }
        }
    }
    for (int i = 1;i <= q;i++) W(ans[i]);
}