#include<bits/stdc++.h>
using namespace std;

const int N=200010,M=21;
int n,q,k,a[N],st[M][N],lg[N],s[N],lst;
inline int qmax(int l,int r){
	int g=lg[r-l+1];
	return max(st[g][l],st[g][r-(1<<g)+1]);
}

int main(){
    freopen("coin.in","r",stdin);
    freopen("coin.out","w",stdout);
	cin>>n>>q>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		s[i]=s[i-1]+(a[i]!=0);
		st[0][i]=a[i];
	}
	for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
	for(int i=1;i<M;i++)
		for(int j=1;j+(1<<i)-1<=n;j++)
			st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
	while(q--){
		int l,r;
		cin>>l>>r;
		if(k==2)l^=lst,r^=lst;
		if(l>r)swap(l,r);
		int ans=qmax(l,r)+s[r]-s[l-1];
		cout<<ans<<endl;
		lst=ans;
	}
	return 0;
}