#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200005];
int f[200005][20],fm[200005][20];
signed main(){
    freopen("coin.in","r",stdin);
    freopen("coin.out","w",stdout);
    int n,k2,q;
    cin>>n>>q>>k2;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        f[i][0]=a[i];
        fm[i][0]=a[i];
    }
    for(int j = 1;j<=21;j++){
        for(int i = 1;i<=n-(1<<j)+1;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
            fm[i][j]=min(fm[i][j-1],fm[i+(1<<(j-1))][j-1]);
        }
    }
    int shang=0;
    for(int i = 1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        if(k2==2)l^=shang,r^=shang;
        //cout<<"r"<<l<<" "<<r<<endl;
        if(l>r)swap(l,r);
        int k=log2(r-l+1);
        int minn=min(fm[l][k],fm[r-(1<<k)+1][k]),maxx=max(f[l][k],f[r-(1<<k)+1][k]);
        int len=r-l+1;
        cout<<minn+1+len-2+maxx-minn+1<<endl;
        shang=minn+1+len-2+maxx-minn+1;
    }
    
    return 0;
}