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.util.*;
import java.io.*;

public class Main {
	
	int max;

	class Data {
		int leftX, rightX;
		int leftConst, rightConst;
		
		public Data(int leftX, int rightX, int leftConst, int rightConst) {
			this.leftX = leftX;
			this.rightX = rightX;
			this.leftConst = leftConst;
			this.rightConst = rightConst;
		}
		
		int get(int x) {
			if (x <= leftX) {
				return leftConst;
			} else if (x >= rightX) {
				return rightConst;
			} else {
				return leftConst + (x - leftX);
			}
		}
		
		Data up(int value) {
			if (leftConst + value >= max) {
				return new Data(0, 0, max, max);
			} else if (rightConst + value >= max) {
				int diff = rightConst + value - max;
				return new Data(leftX, rightX - diff, leftConst + value, max);
			} else {
				return new Data(leftX, rightX, leftConst + value, rightConst + value);
			}
		}
		
		Data down(int value) {
			if (rightConst - value <= 0) {
				return new Data(0, 0, 0, 0);
			} else if (leftConst - value <= 0) {
				int diff = value - leftConst;
				return new Data(leftX + diff, rightX, 0, rightConst - value);
			} else {
				return new Data(leftX, rightX, leftConst - value, rightConst - value);
			}
		}
	}
	
	void solve() {
		max = in.nextInt();
		int k = in.nextInt();
		int[] r = new int[k + 1];
		for (int i = 0; i < k; i++) {
			r[i] = in.nextInt();
		}
		r[k] = (int) 1e9;
		
		
		int q = in.nextInt();
		int[] t = new int[q], a = new int[q];
		for (int i = 0; i < q; i++) {
			t[i] = in.nextInt();
			a[i] = in.nextInt();
		}
		Data cur = new Data(0, max, 0, max);
		
		int ptr = 0;
		for (int i = 0; i < r.length; i++) {
			int prevTime = i == 0 ? 0 : r[i - 1];
			while (ptr < q && t[ptr] <= r[i]) {
				int diff = t[ptr] - prevTime;
				Data ans = null;
				if (i % 2 == 1) {
					ans = cur.up(diff);
				} else {
					ans = cur.down(diff);
				}
				out.println(ans.get(a[ptr++]));
			}
			int diff = r[i] - prevTime;
			prevTime = r[i];
			if (i % 2 == 1) {
				cur = cur.up(diff);
			} else {
				cur = cur.down(diff);
			}
		}
	}

	FastScanner in;
	PrintWriter out;

	void run() {
		in = new FastScanner();
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public FastScanner(String s) {
			try {
				br = new BufferedReader(new FileReader(s));
			} catch (FileNotFoundException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}

		public String nextToken() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
				}
			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextToken());
		}

		public long nextLong() {
			return Long.parseLong(nextToken());
		}

		public double nextDouble() {
			return Double.parseDouble(nextToken());
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}
