// what is matter? never mind.
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
using namespace std;
inline ll read()
{
    char c=getchar();ll x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f
#define mod 333333333333333397
#define ull unsigned long long

int n,m,t,B,id[maxn],cnt[maxn];
int lx[maxn],rx[maxn],ly[maxn],ry[maxn];
ll a[maxn],b[maxn];
ll pw[maxn],w;
vi p[maxn];

inline ll ksc(ll x,ll y,ll zz){
	ll z=(long double)x/mod*y;
	ll res=(ull)x*y-(ull)z*mod;
	return (res+zz+mod)%mod;
}
inline ll add(ll x,ll y){
	return ((x+=y)>=mod)?(x-mod):(x);
}

struct dat{
	ll x; int y;
	dat(ll a=0,int b=0){x=a,y=b;}
	void operator +=(dat b){
		x=ksc(b.x,pw[y],x);
		y+=b.y;
	}
};
dat res[maxn]; 

int tot,su[maxn];
vi pos[2005];
vector<vector<dat>>f[2005];
int idl[maxn],idr[maxn];
int merge(int u,int v){
	if(!u||!v)return u|v;
	int x=++tot;
	pos[x].resize(pos[u].size()+pos[v].size());
	merge(pos[u].begin(),pos[u].end(),pos[v].begin(),pos[v].end(),pos[x].begin());
	int szx=pos[x].size(),szu=pos[u].size(),szv=pos[v].size(),t=0;
	For(i,0,szx-1){
		while(t<szu && pos[u][t]<pos[x][i]) ++t;
		idl[i]=t;
	}
	t=szu-1;
	Rep(i,szx-1,0){
		while(t>=0 && pos[u][t]>pos[x][i]) --t;
		idr[i]=t;
	}
	f[x].resize(szx);
	For(l,0,szx-1){
		f[x][l].resize(szx);
		For(r,l,szx-1)
			if(idl[l]<szu && idr[r]>=0) f[x][l][r]=f[u][idl[l]][idr[r]];
			else f[x][l][r]=dat();
	}
	t=0;
	For(i,0,szx-1){
		while(t<szv && pos[v][t]<pos[x][i]) ++t;
		idl[i]=t;
	}
	t=szv-1;
	Rep(i,szx-1,0){
		while(t>=0 && pos[v][t]>pos[x][i]) --t;
		idr[i]=t;
	}
	For(l,0,szx-1)
		For(r,l,szx-1)
			if(idl[l]<szv && idr[r]>=0)
				f[x][l][r]+=f[v][idl[l]][idr[r]];
	return x;
}
int build(int l,int r){
	if(l>r)return 0;
	if(l==r){
		int x=++tot;
		pos[x].resize(cnt[l]);
		f[x].resize(cnt[l]);
		For(i,0,cnt[l]-1)pos[x][i]=p[l][i];
		For(i,0,cnt[l]-1){
			f[x][i].resize(cnt[l]);
			For(j,i,cnt[l]-1)f[x][i][j]=dat(b[l],1);
		}
		return x;
	}
	int mid=l;
	For(i,l+1,r)
		if(max(su[i]-su[l-1],su[r]-su[i-1])<max(su[mid]-su[l-1],su[r]-su[mid-1])) mid=i;
	return merge(merge(build(l,mid-1),build(mid,mid)),build(mid+1,r));
}

void work(int l,int r){
	tot=0;
	int x=build(l,r);
	int t=0,szx=pos[x].size();
	For(i,1,n){
		while(t<szx && pos[x][t]<i) ++t;
		idl[i]=t;
	}
	t=szx-1;
	Rep(i,n,1){
		while(t>=0 && pos[x][t]>i) --t;
		idr[i]=t;
	}
	For(i,1,m){
		if(ry[i]<l||ly[i]>r)continue;
		if(ly[i]<=l&&ry[i]>=r){
			if(idl[lx[i]]<=idr[rx[i]])
				res[i]+=f[x][idl[lx[i]]][idr[rx[i]]];
			continue;
		}
		int L=max(l,ly[i]),R=min(r,ry[i]);
		For(j,L,R){
			auto it=lower_bound(p[j].begin(),p[j].end(),lx[i]);
			if(it!=p[j].end() && (*it)<=rx[i]) res[i]+=dat(b[j],1); 
		}	
	}
}

int sums[maxn];
void brute(int x){
	For(i,1,n)sums[i]=sums[i-1]+(id[i]==x);
	For(i,1,m)
		if(ly[i]<=x&&ry[i]>=x&&sums[rx[i]]!=sums[lx[i]-1]) res[i]+=dat(b[x],1);
}

signed main()
{
//	freopen("my.out","w",stdout);
	n=read(),w=read(),m=read();
	*pw=1;
	For(i,1,n)pw[i]=(__int128)pw[i-1]*w%mod;
	For(i,1,n)a[i]=b[i]=read();
	sort(b+1,b+n+1),t=unique(b+1,b+n+1)-b-1;
	For(i,1,n){
		id[i]=lower_bound(b+1,b+t+1,a[i])-b;
		p[id[i]].pb(i),++cnt[id[i]];
	}
	For(i,1,m){
		lx[i]=read(),rx[i]=read();
		ll L=read(),R=read(); 
		ly[i]=lower_bound(b+1,b+t+1,L)-b;
		ry[i]=upper_bound(b+1,b+t+1,R)-b-1;
	}
	B=sqrt(n)*0.8;
	For(i,1,t)su[i]=su[i-1]+cnt[i];
	For(l,1,t){
		if(cnt[l]>B){brute(l);continue;}
		int r=l;
		while(r+1<=t && su[r+1]-su[l-1]<=2*B) ++r;
		work(l,r);
		l=r;
	}
	For(i,1,m)printf("%lld\n",res[i].x);
	return 0;
}