#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
const int maxn = 1e6+10;

struct{int64_t sum;int cnt,ls,rs;}t[maxn*21];
int tot;
void ins(int&x,int l,int r,int p,int v){
	t[++tot]=t[x];x=tot;++t[x].cnt,t[x].sum+=v;
	if(l==r)return;
	if(p<=mid)ins(t[x].ls,l,mid,p,v);
	else ins(t[x].rs,mid+1,r,p,v);
}
int64_t get(int u,int v,int p){
	if(p>=t[u].cnt)return t[u].sum;
	int les=t[u].ls[t].cnt-t[v].ls[t].cnt;
	return p<=les?get(t[u].ls,t[v].ls,p):
		t[u].ls[t].sum-t[v].ls[t].sum+get(t[u].rs,t[v].rs,p-les);
}
int n,Q;
int a[maxn],ih[maxn],ihc;
int rt[maxn];
signed main() {
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>n>>Q;
	for(int i=1;i<=n;++i)cin>>a[i],ih[i]=a[i];
	sort(ih+1,ih+n+1);
	for(int i=1,_;i<=n;++i)ins(rt[i]=rt[i-1],1,n,
		_=lower_bound(ih+1,ih+n+1,a[i])-ih,a[i]),--ih[_];
	while(Q--){
		int l,r,k,x,y;cin>>l>>r>>k>>x>>y;
		cout<<get(rt[min(l-1+y+k,r)],rt[l-1],y)-get(rt[min(l-1+x-1+k,r)],rt[l-1],x-1)<<'\n';
	}
}