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.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;


public class N701 {
	static PrintWriter out;
	static Scanner sc;
	static ArrayList<Integer>q,w;
	static ArrayList<Integer>adj[];
	static HashSet<Integer>primesH;
	static boolean prime[];
	//static ArrayList<Integer>a;
	static HashSet<Long>h,tmp;
	static boolean[]v;
	static int[]a,b,c,d;
	static long[]l,dp;
	static char[][]mp;
	static int A,B,n;
	public static void main(String[]args) throws IOException {
		sc=new Scanner(System.in);
		out=new PrintWriter(System.out);
	//	A();
		B();
		//C();
		//D();
		//E():
		//minimum for subarrays of fixed length
		//F();
		out.close();
	}
	  private static void A() throws IOException {
		  int t=ni();
			while(t-->0) {
				int a=sc.nextInt(),b=sc.nextInt();
				if(a<b) {
					out.println(1);
				}else if(a==b)out.println(2);
				else {
					int ans=0;
					if(b==1) {
						ans++;
						b++;
					}
					int temp=ans;
					while(true) {
						int k=a;
						int cnd=temp;
						while(k!=0) {
							k/=b;
							cnd++;
						}
						if(cnd<=ans)break;
						ans=Math.max(cnd, ans);
						b++;
					}
					out.println(ans);
				}
			}
		
	   }
		static void B() throws IOException {
			int t=1;
			while(t-->0) {
				int n=sc.nextInt(),q=sc.nextInt(),k=sc.nextInt();
				a=nai(n);
				int[]vals=new int[n];
				vals[0]=a[0]-1;
				vals[n-1]=k-a[n-1];
				for(int i=1;i<n-1;i++) {
					vals[i]=a[i+1]-a[i-1]-2;
				}
				int []dp=new int[n];
				dp[0]=vals[0];
				for(int i=1;i<n;i++) {
					dp[i]=dp[i-1]+vals[i];
				}
				//disp(dp);
				for(int i=0;i<q;i++) {
					int l=sc.nextInt()-1,r=sc.nextInt()-1;
					if(l==r)out.println(k-1);
					else {
						int ans=0;
//						if(l==0) {
//							ans+=dp[0];
//							l++;
//						}else {
							//int h=k;
//							if(l<n-1) {
//								h=a[l+1];
//							}
							ans+=(a[l+1]-2);
							l++;
						//}
					//	if(r>0) {
							ans+=(k-a[r-1]-1);
							r--;
//						}else  {
//							int h=0;
////							if(r>0) {
////								h=a[r-1];
////							}
//							ans+=(a[r+1]-h-2);
//							r--;
//						}
						
						
						if(l<=r) {
							ans+=dp[r]-dp[l-1];
						}
						out.println(ans);
					}
					
				}
			}
		}
	  static void C() throws IOException {
		  int n=ni();
		  
		  
		}



	static void D() throws IOException {
		int n=ni();
		
		
	}
	static void E() throws IOException {
		int t=ni();
		while(t-->0) {

			int n=ni();
			
		}
		
		
		
	}
	static void F() throws IOException{
		int t=ni();
		while(t-->0) {

			int n=ni();
			
		}
		
	}
	private static void disp(int[] revl) {
		for(int i=0;i<revl.length;i++) {
			out.print(revl[i]+" ");
		}
		out.println();
	}
	static class Pair implements Comparable<Pair>{
		int a,b,A,B;
		Pair(int a,int b,int A,int B){
			this.a=a;
			this.b=b;
			this.A=A;
			this.B=B;
		}
		@Override
		public int compareTo(Pair p) {
			int times1=(int)Math.ceil(b/(double)A);
			int ded1=a*times1;
			int x1=ded1-a;
			int times2=(int)Math.ceil(p.b/(double)A);
			int ded2=p.a*times2;
			int x2=ded2-p.a;
//			if(b%A==0)return 1;
//			if(p.b%A==0)return -1;
			return p.a==a?b-p.b:a-p.a;
//			return a-p.a;
//			return b-p.b;
		}
		public String toString() {
			return "("+a+" "+b+")";
		}
	}
	static int ni() throws IOException {
		return sc.nextInt();
	}
	static double nd() throws IOException {
		return sc.nextDouble();
	}
	static long nl() throws IOException {
		return  sc.nextLong();
	}
	static String ns() throws IOException {
		return sc.next();
	}
	static int[] nai(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
		return a;
	}
	static long[] nal(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextLong();
		return a;
	}
	static int[][] nmi(int n,int m) throws IOException{
		int[][]a=new int[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextInt();
			}
		}
		return a;
	}

	static long[][] nml(int n,int m) throws IOException{
		long[][]a=new long[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextLong();
			}
		}
		return a;
	}
	static void o(String x) {
		out.print(x);
	}
	static void ol(String x) {
		out.println(x);
	}
	static void ol(int x) {
		out.println(x);
	}
	static void disp1(int []a) {
		for(int i=0;i<a.length;i++) {
			out.print(a[i]+" ");
		}
		out.println();
	}
	static void disp2(Pair []a) {
		for(int i=0;i<a.length;i++) {
			out.print(a[i]+" ");
		}
		out.println();
	}
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public boolean hasNext() {return st.hasMoreTokens();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
			
		public boolean ready() throws IOException {return br.ready(); }
		

	}
}
