我们可以把从v到1的路径分成两部分，一半全开车，一半全走路
也就是说要枚举n个节点作为断点(假设当前断点为u)，这个断点是可行解与最优解当且仅当存：在一条从v到u的路径可以全部开车且从u到1全部走路的最短路是满足上一条件中最短的
从v出发开车可以到的点， 一定满足路径上所有边海拔都高于水位
Kruskal重构树:
这里已经很明显可以用Kruskal重构树求解了
我们把每条边按海拔降序排序，重构树完成后，对于每次询问，找到树中深度最小且海拔大于水位的节点，那么他的子树的全部节点都可以由v开车到达
这一点可以由重构树是小根堆的性质简单得证，即每个节点子树内所有节点海拔都比该节点大
现在要求的最后一步就是这个子树内所有节点到1号节点的步行最短路， 因为是无向图，所以一开始预处理1节点到所有节点最短路就好，然后dfs可以顺便求出某个节点子树内的最短路
--
(ps)：
这个题卡 (SPFA) CCF怎么能这样对我可爱的SPFA
所以必须打迪杰斯特拉
处理细节：
- 莫名卡常（可能是我不优秀），对于一些数组不用清零的就别清了，比如倍增数组和最小值数组（删了HSYOJ就过了）
- 克鲁斯卡尔重构树套路：清零!!!（数据不清空，爆零两行泪）
可持久化并查集
一定程度上，可持久化并查集的适用范围是大于克鲁斯卡尔重构树的，虽然在这里不是最优秀的做法，把(NlogN)的复杂度硬生生变成了(Nlog^2N)（卡卡常也是能过的），这里虽然不是正解，但也是一个好方案
做法：
迪杰斯特拉预处理，然后可持久化并查集维护联通块（口胡完了）
实现细节：
注意常数
代码：
（这里用的是Kruskal重构树）
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define ll long long
#define re register
#define gc getchar()
inline int read()
{
re int x(0),f(1);re char ch(gc);
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=gc;}
while(ch>='0'&&ch<='9') x=(x*10)+(ch^48),ch=gc;
return x*f;
}
const int N=8e5+10;
int h[N],cnt,n,m,f[N][22],tot;
ll val[N],_min[N],dis[N];
struct edge{int next,to;ll w;}e[N<<1];
void add(int u,int v,ll w){e[++cnt]=(edge){h[u],v,w},h[u]=cnt;}
#define QXX(u) for(int i=h[u],v;v=e[i].to,i;i=e[i].next)
struct node{int u,v;ll h;}E[N<<1];
bool operator < (node a,node b){return a.h>b.h;}
struct Node{ll x;int id;};
bool operator < (Node a,Node b){return a.x<b.x;}
priority_queue <Node> q;
int vis[N];
int fa[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void djs()
{
memset(vis,0,sizeof(vis));
memset(dis,127,sizeof(dis));
q.push((Node){0,1});
dis[1]=0;
while(!q.empty())
{
Node t=q.top();q.pop();
int u=t.id;
if(vis[u]) continue;
vis[u]=1;
QXX(u)
if(dis[u]+e[i].w<dis[v])
{
dis[v]=dis[u]+e[i].w;
q.push((Node){-dis[v],v});
}
}
}
void dfs(int u)
{
_min[u]=dis[u];
QXX(u)
{
f[v][0]=u;
dfs(v);
_min[u]=min(_min[u],_min[v]);
}
}
void kruskal()
{
memset(h,0,sizeof(h));
cnt=0;
sort(E+1,E+1+m);
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i)
{
int u=find(E[i].u),v=find(E[i].v);
if(u!=v)
{
val[++tot]=E[i].h;
fa[u]=fa[v]=fa[tot]=tot;
add(tot,u,0),add(tot,v,0);
}
}
dfs(tot);
}
int main()
{
// freopen("return.in","r",stdin);
int T=read();
while(T--)
{
memset(h,0,sizeof(h));
memset(f,0,sizeof(f));
memset(_min,127,sizeof(_min));
n=read(),m=read(),cnt=0;tot=n;
for(int i=1;i<=m;++i)
{
re int u=read(),v=read(),w=read(),h=read();
add(u,v,w),add(v,u,w);
E[i].u=u,E[i].v=v,E[i].h=h;
}
djs();
kruskal();
for(int i=1;(1<<i)<=tot;i++)
for(int u=1;u<=tot;u++)
f[u][i]=f[f[u][i-1]][i-1];
int Q=read(),K=read(),S=read();
ll la=0;
while(Q--)
{
int vi=read(),pi=read();
vi=(vi+K*la-1)%n+1;
pi=(pi+K*la)%(S+1);
for(int j=21;j>=0;--j)
if(f[vi][j]&&val[f[vi][j]]>pi)
vi=f[vi][j];
la=_min[vi];
cout<<la<<endl;
}
}
return 0;
}