We have a sandglass consisting of two bulbs, bulb A and bulb B. These bulbs contain some amount of sand. When we put the sandglass, either bulb A or B lies on top of the other and becomes the upper bulb. The other bulb becomes the lower bulb.

The sand drops from the upper bulb to the lower bulb at a rate of 1 gram per second. When the upper bulb no longer contains any sand, nothing happens.

Initially at time 0, bulb A is the upper bulb and contains a grams of sand; bulb B contains X-a grams of sand (for a total of X grams).

We will turn over the sandglass at time r_1,r_2,..,r_K. Assume that this is an instantaneous action and takes no time. Here, time t refer to the time t seconds after time 0.

You are given Q queries. Each query is in the form of (t_i,a_i). For each query, assume that a=a_i and find the amount of sand that would be contained in bulb A at time t_i.

Constraints

* 1≤X≤10^9
* 1≤K≤10^5
* 1≤r_1<r_2< .. <r_K≤10^9
* 1≤Q≤10^5
* 0≤t_1<t_2< .. <t_Q≤10^9
* 0≤a_i≤X (1≤i≤Q)
* All input values are integers.

Input

The input is given from Standard Input in the following format:


X
K
r_1 r_2 .. r_K
Q
t_1 a_1
t_2 a_2
:
t_Q a_Q


Output

For each query, print the answer in its own line.

Examples

Input

180
3
60 120 180
3
30 90
61 1
180 180


Output

60
1
120


Input

100
1
100000
4
0 100
90 100
100 100
101 100


Output

100
10
0
0


Input

100
5
48 141 231 314 425
7
0 19
50 98
143 30
231 55
342 0
365 100
600 10


Output

19
52
91
10
58
42
100
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        D solver = new D();
        solver.solve(1, in, out);
        out.close();
    }

    static class D {
        final int LG = 20;

        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int x = in.nextInt();
            int k = in.nextInt();
            long[] r = new long[k + 2];
            for (int i = 0; i < k; i++) {
                r[i + 1] = in.nextInt();
            }
            r[k + 1] = 1_000_000_001;
            k += 2;

            long[] sa = new long[k];
            int[] dnext = new int[k];
            boolean[] peak = new boolean[k];
            peak[0] = true;
            int d = -1;
            for (int i = 1; i < k; i++) {
                sa[i] = sa[i - 1] + d * (r[i] - r[i - 1]);
                dnext[i - 1] = d;
                d = -d;
                peak[i] = !peak[i - 1];
            }

            RT rt = new RT(k);
            int[][] next = new int[LG][k + 1];
            next[0][k] = k;
            for (int i = k - 1; i >= 0; i--) {
                if (peak[i]) {
                    int nl = rt.firstL(sa[i] - x);
                    int nr = rt.firstG(sa[i]);
                    next[0][i] = Math.min(nl, nr);
                } else {
                    int nl = rt.firstL(sa[i]);
                    int nr = rt.firstG(sa[i] + x);
                    next[0][i] = Math.min(nl, nr);
                }
                if (i > 0) {
                    rt.update(i, sa[i]);
                }
            }

            for (int p = 1; p < LG; p++) {
                for (int j = 0; j <= k; j++) {
                    next[p][j] = next[p - 1][next[p - 1][j]];
                }
            }

            int q = in.nextInt();
            for (int i = 0; i < q; i++) {
                long t = in.nextLong();
                long a = in.nextLong();

                int L = 0;
                int R = k;
                while (L < R - 1) {
                    int M = (L + R) / 2;
                    if (r[M] <= t) {
                        L = M;
                    } else {
                        R = M;
                    }
                }

                int tp = L;

                int nl = rt.firstL(-a);
                int nr = rt.firstG(x - a);
                int np = Math.min(nl, nr);

                long ans;
                if (np <= tp) {
                    int st = LG - 1;
                    while (st >= 0) {
                        if (next[st][np] > tp) {
                            st--;
                        } else {
                            np = next[st][np];
                        }
                    }
                    if (peak[np]) {
                        a = x - sa[np];
                    } else {
                        a = -sa[np];
                    }
                    ans = a + sa[tp] + (t - r[tp]) * dnext[tp];
                } else {
                    ans = a + sa[tp] + (t - r[tp]) * dnext[tp];
                }
                if (ans < 0) {
                    ans = 0;
                }
                if (ans > x) {
                    ans = x;
                }
                out.println(ans);
            }
        }

        class RT {
            int n;
            long[] a;
            long[] b;

            RT(int n) {
                this.n = n;
                a = new long[4 * n];
                Arrays.fill(a, Integer.MAX_VALUE);
                b = new long[4 * n];
                Arrays.fill(b, Integer.MIN_VALUE);
            }

            int firstL(long v) {
                return firstL(0, 0, n, v);
            }

            int firstL(int p, int L, int R, long v) {
                if (a[p] > v) {
                    return n;
                }
                if (L == R - 1) {
                    return L;
                }
                int M = (L + R) / 2;
                if (a[2 * p + 1] > v) {
                    return firstL(2 * p + 2, M, R, v);
                }
                return firstL(2 * p + 1, L, M, v);
            }

            int firstG(long v) {
                return firstG(0, 0, n, v);
            }

            int firstG(int p, int L, int R, long v) {
                if (b[p] < v) {
                    return n;
                }
                if (L == R - 1) {
                    return L;
                }
                int M = (L + R) / 2;
                if (b[2 * p + 1] < v) {
                    return firstG(2 * p + 2, M, R, v);
                }
                return firstG(2 * p + 1, L, M, v);
            }

            void update(int i, long v) {
                update(0, 0, n, i, v);
            }

            void update(int p, int L, int R, int i, long v) {
                if (L == R - 1) {
                    a[p] = b[p] = v;
                    return;
                }

                int M = (L + R) / 2;
                if (i < M) {
                    update(2 * p + 1, L, M, i, v);
                } else {
                    update(2 * p + 2, M, R, i, v);
                }
                a[p] = Math.min(a[2 * p + 1], a[2 * p + 2]);
                b[p] = Math.max(b[2 * p + 1], b[2 * p + 2]);
            }

        }

    }
}

