WA 30pts

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=400005;
const int M=800005;
struct edge{
	int v;
	int nxt;
	int w;
}edge[M];
int head[N],cnt;
int val[N];//重构树点权
struct T{
	int u,v,h;
	bool operator <(const T &rhs)const{
		return h>rhs.h;
	}
}e[M];
int T;
int n,m,q,k,s,tot;
int dis[N],vis[N];
int fa[N];
int f[N][20];
void init(){
	cnt=0;
	memset(head,0,sizeof(head));
}
void addedge(int u,int v,int w){
	edge[++cnt].v=v,edge[cnt].w=w,edge[cnt].nxt=head[u],head[u]=cnt;
}
void dijkstra(){
	memset(vis,0,sizeof(vis));
	memset(dis,0x7f,sizeof(dis));
	priority_queue<pair<int,int> > q;
	q.push(make_pair(1,0));
	dis[1]=0;
	while(!q.empty()){
		int u=q.top().first;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].v;
			if(dis[v]>dis[u]+edge[i].w){
				dis[v]=dis[u]+edge[i].w;
				if(!vis[v]) q.push(make_pair(v,dis[v]));
			}
		}
	}
}
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void kruscal(){
	sort(e+1,e+1+m);
	tot=n;
	for(int i=1;i<=2*n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int fu=find(e[i].u),fv=find(e[i].v);
		if(fu!=fv){
			fa[fu]=fa[fv]=++tot;
			val[tot]=e[i].h;
			dis[tot]=min(dis[fu],dis[fv]);
			f[fu][0]=f[fv][0]=tot;
		}
	}
	for(int j=1;(1<<j)<=tot;j++){
		for(int i=1;i<=tot;i++){
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%lld",&T);
	while(T--){
		init();
		scanf("%lld%lld",&n,&m);
		for(int i=1;i<=m;i++){
			int u,v,l,a;
			scanf("%lld%lld%lld%lld",&u,&v,&l,&a);
			addedge(u,v,l);
			addedge(v,u,l);
			e[i].u=u,e[i].v=v,e[i].h=a;
		}
		dijkstra();
		kruscal();
		scanf("%lld%lld%lld",&q,&k,&s);
		int lastans=0;
		while(q--){
			int v,p;
			scanf("%lld%lld",&v,&p);
			v=(v+k*lastans-1)%n+1;
			p=(p+k*lastans)%(s+1);
			for(int i=19;i>=0;i--){
				if(f[v][i]&&val[f[v][i]]>p) v=f[v][i];
			}
			lastans=dis[v];
			printf("ans:%lld\n",dis[v]);
		}
	}
	return 0;
}