#include<bits/stdc++.h>
#define ll long long
#define N 200005
using namespace std;
inline char nc(){
	static char buf[1000000],*p=buf,*q=buf;
	return p==q&&(q=(p=buf)+fread(buf,1,1000000,stdin),p==q)?EOF:*p++;
}
inline ll read(){
	ll res = 0;
	char c = nc();
	while(c<'0'||c>'9')c=nc();
	while(c<='9'&&c>='0')res=res*10+c-'0',c=nc();
	return res;
}
char obuf[1<<21],*p3=obuf; 
inline void pc(char c){ 
	p3-obuf<=(1<<20)?(*p3++=c):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=c); 
} 
inline void write(ll x){ 
	if(x<0) pc('-'),x=-x; 
	if(x>9) write(x/10); 
	pc(x%10+'0'); 
}
struct node{ll x,y,id;}p[N];
bool cmp(node a,node b){return a.x<b.x;}
ll n,q,s,i,j,a[N],b[N],l[N],r[N],id[N],ls,rs,ans[N],qzh[N],cnt[N],sum,tr[N<<2],tr2[N<<2];
multiset<ll> que;
inline void add(ll x,ll c,ll s,ll t,ll p){
	if(s==t){
		tr[p]+=c,tr2[p]+=c*qzh[s];
		return ;
	}
	if(x<=(s+t)/2) add(x,c,s,(s+t)/2,2*p);
	else add(x,c,(s+t)/2+1,t,2*p+1);
	tr[p]=tr[2*p]+tr[2*p+1],tr2[p]=tr2[2*p]+tr2[2*p+1];
}
inline ll query(ll x,ll s,ll t,ll p){
	if(!x) return 0;
	if(x==tr[p]) return tr2[p];
	if(x>=tr[2*p]) return tr2[2*p]+query(x-tr[2*p],(s+t)/2+1,t,2*p+1);
	else return query(x,s,(s+t)/2,2*p);
}
inline void solve(){
	n=read(),q=read(),s=read(),ls=rs=s;
	for(i=1;i<=n;i++) a[i]=read(),b[i]=read(),l[i]=read(),r[i]=read(),qzh[i]=b[i]-a[i],cnt[i]=i;
	sort(qzh+1,qzh+n+1);
	for(i=1;i<=n;i++) id[i]=(cnt[lower_bound(qzh+1,qzh+n+1,b[i]-a[i])-qzh]++);
	for(i=1;i<=q;i++) p[i].x=read(),p[i].y=read(),p[i].id=i;
	sort(p+1,p+q+1,cmp);
	for(i=1,j=1,sum=0;i<=n;i++){
		ls--,rs++,sum+=a[i],add(id[i],1,1,n,1),que.insert(id[i]);
		ll nls = max(l[i],ls),nrs = min(r[i],rs);
		if(nls%2!=ls%2) nls++;
		if(nrs%2!=rs%2) nrs--;
		if(nls>nrs){
			for(;j<=q;j++) ans[p[j].id]=-1;
			break;
		}
		if(nls!=ls){
			ll cnt = (nls-ls)/2;
			sum+=query(cnt,1,n,1);
			while(cnt--) add(*que.begin(),-1,1,n,1),que.erase(que.begin());
		}
		if(nrs!=rs){
			ll cnt = (rs-nrs)/2;
			while(cnt--) add(*--que.end(),-1,1,n,1),que.erase(--que.end());
		}
		ls=nls,rs=nrs;
		while(j<=q&&p[j].x==i){
			if(p[j].y<ls||p[j].y>rs) ans[p[j].id]=-1;
			else if(p[j].y%2!=ls%2) ans[p[j].id]=-1;
			else ans[p[j].id]=sum+query((p[j].y-ls)/2,1,n,1);
			j++;
		}
	}
	for(i=1;i<=q;i++) write(ans[i]),pc('\n');
}
inline void clear(){
	memset(tr,0,sizeof(tr));
	memset(tr2,0,sizeof(tr2));
	que.clear();
}
int main(){
	ll T;
	T=read();
	while(T--) solve(),clear();
	return fwrite(obuf,p3-obuf,1,stdout),0;
}