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].
#include<bits/stdc++.h>
#define fi                first
#define se                 second
#define ll               long long
#define mod              1000000007LL
#define endl              "\n"
#define fast               ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb                push_back
#define all(v)             v.begin(),v.end()
#define inp(V,n)      for(int i=0;i<n;i++){cin >> V[i];}
#define oup(V,n)     {for(int i=0;i<n;i++){cout <<  V[i] << " "  ;} cout << endl;}
#define pll              pair<long long,long long>
#define pi            3.141592653589793238
using namespace std;
//vector<ll> adj[5000005];
//vector<bool> vis(3000005,false);
ll factorial(ll n)
{
    return (n == 1 || n == 0) ? 1 : n * factorial(n - 1);
}
ll gcd(ll a, ll b)
{
    if (a == 0)
      return b;
    return gcd(b % a, a);
}
ll lcm(ll a, ll b)
{
   return (a*b)/gcd(a, b);
}
bool sortByVal(const pair<ll,ll> &a,
              const pair<ll,ll> &b)
{
      if(a.fi == b.fi)
        return a.se < b.se;
     else
        return a.fi > b.fi;
}
ll Powb(ll b,ll n)
{
    if(n==0) return 1LL;
    if(n==1) return b;
    ll temp = Powb(b,n/2);
    if(n%2==0){return (temp*temp)%mod;}
    else{return (b*((temp*temp)%mod))%mod;}
}
int main()
{
 fast;
     int t=1;
     //cin>>t;
     while(t--)
     {
     ll q,i,j,m,n,k,sum=0,c=0,d=0,e=0,f=0,g=0,h=0,maxi=0;
      cin>>n>>q>>k;
      vector<ll> a(n);
      inp(a,n);
      vector<ll> b(n);
      if(n == 1)
      {
          while(q--)
          {
              cin>>c>>d;
              cout<<k-1<<endl;
          }
      }
      else
      {
          for(i=0;i<n;i++)
          {
              if(i == 0)
              {
                  c=a[i+1]-2;
                  b[i]=c;
              }
              else if(i == n-1)
              {
                  c=k-a[n-1];
                  b[i]=c;
              }
              else
              {
                  c=a[i-1];
                  d=a[i+1];
                  d-=c;
                  d-=2;
                  b[i]=d;
              }

          }
          vector<ll> p(n);
          sum=0;
          for(i=0;i<n;i++)
          {
              sum+=b[i];
              p[i]=sum;
          }

          //oup(b,n);
          //oup(p,n);
          while(q--)
          {
              sum=0;
              cin>>c>>d;
              c--;
              d--;
              if(c == d)
              {
                  cout<<k-1<<endl;
              }
              else if((d-c) == 1)
              {
                  e=a[d]-2;
                  f=k-a[c]-1;
                  cout<<e+f<<endl;
              }
              else
              {
                  sum=p[d-1]-p[c];
                  e=k-a[d-1]-1;
                  sum+=e;
                  f=a[c+1]-2;
                  sum+=f;
                  cout<<sum<<endl;
              }

          }
      }


     }
}
