记录编号	539500	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2018]归程	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	12.642 s
提交时间	2019-08-07 16:11:27	内存使用	264.67 MiB

#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
struct P
{
	int x,y,a,l;
};
P t[800001],ls[800001],nt[800001];
int headl[800001],headn[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,tot1,tot2;
priority_queue<pair<long long int,long long int> > q;
void ADDL(int x,int y,int dis)
{
	ls[++tot1].l=dis;
	ls[tot1].y=y;
	ls[tot1].a=headl[x];
	headl[x]=tot1; 
}
void ADDN(int x,int y)
{
	nt[++tot2].y=y;
	nt[tot2].a=headn[x];
	headn[x]=tot2;
}
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=headl[u];i;i=ls[i].a)
		{
			long long int v=ls[i].y;
			if(dis[u]+ls[i].l<dis[v])
			{
				dis[v]=dis[u]+ls[i].l;
				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=headn[x];i;i=nt[i].a)
	{
		gra[nt[i].y][0]=x;
		DFS(nt[i].y);
		far[x]=min(far[x],far[nt[i].y]);
	}
}
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("noi2018_return.in","r",stdin);
	freopen("noi2018_return.out","w",stdout);
	T=read();
	while(T--)
	{
		memset(gra,0,sizeof(gra)); 
		memset(far,0,sizeof(far));
		memset(val,0,sizeof(val));
		memset(headl,0,sizeof(headl));
		memset(headn,0,sizeof(headn));
		tot1=tot2=0;
		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));
			ADDL(a1,a2,a3);
			ADDL(a2,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;
				ADDN(cnt,xl);
				ADDN(cnt,yl);
				//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;
}