记录编号	539498	评测结果	AAAAATAAATTTTTAATTTT
题目名称	3164.[NOI 2018]归程	最终得分	50
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	未通过
代码语言	C++	运行时间	41.425 s
提交时间	2019-08-07 15:55:22	内存使用	267.72 MiB

#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
struct P
{
	int x,y,a;
};
P t[800001];
vector<pair<int,long long int> >ls[800001];
vector<long long int> nt[800001];
long long int val[800001];
bool vis[800001];
long long int dis[800001];
long long int fat[800001];
long long int T,n,m,a1,a2,a3,a4,cnt,Q,K,S;
priority_queue<pair<long long int,long long int> > q;
int FIND(long long int x)
{
	if(x==fat[x])
	{
		return x;
	}
	return fat[x]=FIND(fat[x]);
}
void DIJ()
{
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f3f3f3f,sizeof(dis));
	dis[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty())
	{
		long long int u=q.top().second;
		q.pop();
		if(vis[u])
			continue;
		vis[u]=1;
		for(int i=0;i<ls[u].size();i++)
		{
			long long int v=ls[u][i].first;
			if(dis[u]+ls[u][i].second<dis[v])
			{
				dis[v]=dis[u]+ls[u][i].second;
				q.push(make_pair(-dis[v],v));
			}
		}
	}
}
bool Function(P a,P b)
{
	return a.a>b.a;
}
long long int far[800001];
long long int gra[800001][30];
void DFS(int x)
{
	far[x]=dis[x];
	for(int i=0;i<nt[x].size();i++)
	{
		gra[nt[x][i]][0]=x;
		DFS(nt[x][i]);
		far[x]=min(far[x],far[nt[x][i]]);
	}
}
long long int read()
{
    long long int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}
int main()
{
	freopen("return.in","r",stdin);
	freopen("return.out","w",stdout);
	T=read();
	while(T--)
	{
		memset(gra,0,sizeof(gra)); 
		for(int i=0;i<=40000;i++)
		{
			ls[i].clear();
			nt[i].clear();
		}
		memset(far,0,sizeof(far));
		memset(val,0,sizeof(val));
		cnt=0;
		n=read();
		m=read();
		for(int i=1;i<=m;i++)
		{
			a1=read();
			a2=read();
			a3=read();
			a4=read();
			t[i].x=a1;
			t[i].y=a2;
			t[i].a=a4;
			ls[a1].push_back(make_pair(a2,a3));
			ls[a2].push_back(make_pair(a1,a3));
		}
		for(int i=1;i<=n;i++)
		{
			fat[i]=i;
		}
		DIJ();
		sort(t+1,t+1+m,Function);
		cnt=n;
		for(int i=1;i<=m;i++)
		{
			int xl=t[i].x;
			int yl=t[i].y;
			xl=FIND(xl);
			yl=FIND(yl);
			if(xl!=yl)
			{
				++cnt;
				fat[xl]=fat[yl]=fat[cnt]=cnt;
				val[cnt]=t[i].a;
				nt[cnt].push_back(xl);
				nt[cnt].push_back(yl); 
			}
		}
		DFS(cnt);
		for(int i=1;(1<<i)<=cnt;i++)
		{
			for(int j=1;j<=cnt;j++)
			{
				gra[j][i]=gra[gra[j][i-1]][i-1];
			}
		}
		Q=read();
		K=read();
		S=read();
		long long int lastans=0;
		while(Q--)
		{
			a1=read();
			a2=read();
			a1=(a1+K*lastans-1)%n+1;
			a2=(a2+K*lastans)%(S+1);
			for(int j=22;j>=0;--j)
			{
				if(gra[a1][j]&&val[gra[a1][j]]>a2)
				{
					a1=gra[a1][j];
				}
			}
			printf("%lld\n",lastans=far[a1]);
		}
	}
	return 0;
}