Given a positive integer k, two arrays are called k-similar if:

  * they are strictly increasing; 
  * they have the same length; 
  * all their elements are positive integers between 1 and k (inclusive); 
  * they differ in exactly one position. 



You are given an integer k, a strictly increasing array a and q queries. For each query, you are given two integers l_i ≤ r_i. Your task is to find how many arrays b exist, such that b is k-similar to array [a_{l_i},a_{l_i+1}…,a_{r_i}]. 

Input

The first line contains three integers n, q and k (1≤ n, q ≤ 10^5, n≤ k ≤ 10^9) — the length of array a, the number of queries and number k.

The second line contains n integers a_1, a_2, …,a_n (1 ≤ a_i ≤ k). This array is strictly increasing — a_1 < a_2 < … < a_n.

Each of the following q lines contains two integers l_i, r_i (1 ≤ l_i ≤ r_i ≤ n).

Output

Print q lines. The i-th of them should contain the answer to the i-th query.

Examples

Input


4 2 5
1 2 4 5
2 3
3 4


Output


4
3


Input


6 5 10
2 4 6 7 8 9
1 4
1 2
3 5
1 6
5 5


Output


8
9
7
6
9

Note

In the first example:

In the first query there are 4 arrays that are 5-similar to [2,4]: [1,4],[3,4],[2,3],[2,5].

In the second query there are 3 arrays that are 5-similar to [4,5]: [1,5],[2,5],[3,5].
import java.util.*;
import java.io.*;

public class Main {
	static final int M = 1000000007;

	static class FastScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

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

		int nextInt() {
			return Integer.parseInt(next());
		}

		long[] readArrayLong(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		int[] readArrayInt(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		long nextLong() {
			return Long.parseLong(next());
		}
	}

	// sorting template
	static void sortLong(long[] a) {
		ArrayList<Long> l = new ArrayList<>();
		for (long i : a)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < a.length; i++)
			a[i] = l.get(i);
	}

	static void sortInt(int[] a) {
		ArrayList<Integer> l = new ArrayList<>();
		for (int i : a)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < a.length; i++)
			a[i] = l.get(i);
	}

	static class Graph {
		private ArrayList<Integer> adj[];
		public String s;
		public String dpch;

		Graph(int n) {
			adj = new ArrayList[n + 1];
			for (int i = 1; i <= n; i++) {
				adj[i] = new ArrayList<>();
			}
		}

		void addEdges(int u, int v) {
			adj[u].add(v);
			adj[v].add(u);
		}

		void dfs(int v, boolean[] vis, int d) {
			vis[v] = true;
			if (d > maxDist) {
				maxNode = v;
				maxDist = d;
			}
			for (int u : adj[v]) {
				if (!vis[u]) {
					dfs(u, vis, d + 1);
				}
			}
		}

		void bfs(int v, boolean[] vis) {
			Queue<Integer> q = new LinkedList<>();
			q.add(v);
			dist[v] = 0;
			vis[v] = true;
			while (q.size() > 0) {
				int node = q.poll();
				for (int u : adj[node]) {
					if (!vis[u]) {
						vis[u] = true;
						dist[u] = dist[node] + 1;
						q.add(u);
					}
				}
			}
		}
	}

	static class Pair<F, S> {
		F first;
		S second;

		Pair(F first, S second) {
			this.first = first;
			this.second = second;
		}

		public F getFirst() {
			return this.first;
		}

		public S getSecond() {
			return this.second;
		}
		// Sort on basis of first term, reverse p1.first and p2.first to sort in desc
		// Collections.sort(a, (p1, p2) -> (p1.first - p2.first));

		// Sort on the basis of second term, reverse p1.second and p2.second to sort
		// in
		// desc
		// Collections.sort(a, (p1, p2) -> (p1.second - p2.second));
	}

	static int __gcd(int a, int b) {
		if (b == 0)
			return a;
		return __gcd(b, a % b);
	}

	public static int subtree, maxNode, maxDist;
	public static int[] dist;
	public static int[] connected;

	public static void main(String[] args) throws IOException {
		FastScanner fs = new FastScanner();
		int t = 1;
		StringBuffer res = new StringBuffer();
		for (int tt = 1; tt <= t; tt++) {
			int n = fs.nextInt();
			int q = fs.nextInt();
			long k = fs.nextLong();
			long[] a = new long[n + 1];
			for (int i = 1; i <= n; i++) {
				a[i] = fs.nextLong();
			}
			while (q-- > 0) {
				long f = 1;
				int l = fs.nextInt();
				int r = fs.nextInt();
				long count = a[r] - a[l] + k + 1 - 2 * (r - l + 1);
				res.append(count).append("\n");
			}
		}
		System.out.println(res);
	}
}
