#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
#define ll long long
//#define int  unsigned long long
#define pb push_back
//#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int mod = 998244353;
const int N = 1000003;
const int K = 20;
int spmin[K][N], spmax[K][N], p[K][N], d[N], a[N], s[N], tt[N], k, x, lg[N];
int findmin(int l, int r){
    int d = lg[r - l + 1];
    return min(spmin[d][l], spmin[d][r - (1 << d) + 1]);
}
int findmax(int l, int r){
    int d = lg[r - l + 1];
    return max(spmax[d][l], spmax[d][r - (1 << d) + 1]);
}
int solve1(int v, int y){
    int l = v;
    int r = k;
    int L, R;
    if (v % 2){
        R = y + s[v];
        L = -x + y + s[v];
    } else{
        R = x - y + s[v];
        L = -y + s[v];
    }
    while(r - l > 1){
        int mid = (r + l) / 2;
        if (findmax(v, mid) <= R && findmin(v, mid) >= L) l = mid; else r = mid;
    }
    return r;
}
int solve2(int v, int y, int t){
    int l = v;
    int r = k;
    while(r - l > 1){
        int mid = (r + l) / 2;
        if (tt[mid] > t) r = mid; else l = mid;
    }
    int z = s[r - 1] - s[v];
   // cout << "z = " << z << endl;
    if (v % 2 == 0){
        y += z;
    } else{
        y -= z;
    }
    if ((r - v) % 2 == 0) y = x - y;
   // cout << "r = " << r << " " << y << " " << tt[r - 1] << " " << t << " " << s[r - 1] << " " << s[v] << endl;
    y = max(0LL, y + tt[r - 1] - t);
    if (r % 2 == 0) y = x - y;
    return y;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
   // freopen("input.txt", "r", stdin);
    cin >> x >> k;
    for (int i = 1; i <= k; i++){
        cin >> a[i];
    }
    k++;
    a[k] = 1e15;
    for (int i = 1; i <= k; i++){
        int x = a[i] - a[i - 1];
        if (i % 2) d[i] = -x; else d[i] = x;
    }
    for (int i = 1; i <= k; i++){
        s[i] = s[i - 1] + d[i];
        tt[i] = tt[i - 1] + abs(d[i]);
    }
    for (int i = 0; i <= k; i++){
        spmin[0][i] = s[i];
        spmax[0][i] = s[i];
    }
    for (int i = 1; i <= 17; i++){
        for (int j = 0; j <= k; j++){
            if (j >= (1 << i)) lg[j] = i;
            spmin[i][j] = min(spmin[i - 1][j], spmin[i - 1][j + (1 << (i - 1))]);
            spmax[i][j] = max(spmax[i - 1][j], spmax[i - 1][j + (1 << (i - 1))]);
        }
    }
    for (int i = 1; i < k; i++){
        int j = solve1(i, x);
        p[0][i] = j;
    }
    p[0][k] = k;
    for (int i = 1; i <= 17; i++){
        for (int j = 1; j <= k; j++){
            p[i][j] = p[i - 1][p[i - 1][j]];
        }
    }
    int q;
    cin >> q;
    while(q--){
        int t, b;
        cin >> t >> b;
        int j = solve1(0, b);
        int v;
        if (tt[j] <= t){
            v = j;
          //  cout << "j = " << j << endl;
            for (int i = 17; i >= 0; i--){
                if (tt[p[i][v]] <= t){
                    v = p[i][v];
                }
            }

        } else v = 0;
      //  cout << "v = " << v << endl;
        if (v == 0) cout << solve2(v, b, t) << endl;
        else cout << solve2(v, x, t) << endl;
    }
}


Measured memory_bytes: 167936