```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
int u,v,w;
}a[800005];
int to[800005],nx[800005],st[800005],tot;
int dp[800005][25],d[800005];
void add(int u,int v){
to[++tot]=v;
nx[tot]=st[u];
st[u]=tot;
}
bool cmp(node a,node b){
return a.w>b.w;
}
int fa[800005],p[800005];
int find(int p){
if(p==fa[p]) return p;
return fa[p]=find(fa[p]);
}
int sum;
void dfs(int u,int fa){
for(int i=st[u];i;i=nx[i]){
int v=to[i];
if(v==fa) continue;
dp[v][0]=u;
d[v]=d[u]+1;
dfs(v,u);
}
}
void zhuanyi(){
for(int i=1;i<=20;i++){
for(int j=1;j<=2*n;j++){
dp[j][i]=dp[dp[j][i-1]][i-1];
}
}
}
int LCA(int u,int v){
if(d[u]<d[v]) swap(u,v);
int p=d[u];
for(int i=20;i>=0;i--){
if(p-pow(2,i)>=d[v]){
p-=pow(2,i);
u=dp[u][i];
}
}
if(u==v) return v;
for(int i=20;i>=0;i--){
if(dp[u][i]!=dp[v][i]){
u=dp[u][i];
v=dp[v][i];
}
}
return dp[u][0];
}
int to1[800005],nx1[800005],st1[800005],zhi1[800005],tot1;
void add1(int u,int v,int w){
to1[++tot1]=v;
zhi1[tot1]=w;
nx1[tot1]=st1[u];
st1[u]=tot1;
}
struct node1{
long long w,num;
bool operator <(const node1 &b) const{
return w>b.w;
}
};
int dis[400005],vis[400005];
void dij(){
node1 start;
start.num=1;
start.w=0;
memset(dis,0X3f,sizeof(dis));
dis[1]=0;
priority_queue<node1> q;
q.push(start);
while(!q.empty()){
node1 cur=q.top();
q.pop();
if(vis[cur.num]) continue;
vis[cur.num]=1;
for(int i=st1[cur.num];i;i=nx1[i]){
int v=to1[i];
if(dis[v]>dis[cur.num]+zhi1[i]){
dis[v]=dis[cur.num]+zhi1[i];
node1 next;
next.num=v;
next.w=dis[v];
q.push(next);
}
}
}
}
int bei(int v,int s){
int u=v;
if(s==0) return 1;
for(int i=20;i>=0;i--){
if(p[dp[u][i]]>s&&dp[u][i]!=0){
u=dp[u][i];
}
}
return u;
}
int r[400005];
int main(){
int t;
cin>>t;
while(t--){
scanf("%d%d",&n,&m);
memset(dp,0,sizeof(dp));
for(int i=1;i<=m;i++){
int pop;
scanf("%d%d%d%d",&a[i].u,&a[i].v,&pop,&a[i].w);
add1(a[i].u,a[i].v,pop);
add1(a[i].v,a[i].u,pop);
}
dij();
for(int i=1;i<=2*n;i++) fa[i]=i;
sum=n;
sort(a+1,a+m+1,cmp);
int ans=0;
for(int i=1;i<=n;i++){
r[i]=i;
}
for(int i=1;i<=m;i++){
int x=find(a[i].u),y=find(a[i].v);
if(x==y) continue;
sum++;
fa[x]=fa[y]=fa[sum]=sum;
p[sum]=a[i].w;
if(dis[r[x]]>dis[r[y]]){
r[sum]=r[y];
}
else{
r[sum]=r[x];
}
add(sum,x);
add(x,sum);
add(sum,y);
add(y,sum);
ans++;
if(ans==n-1) break;
}
for(int i=0;i<=20;i++) dp[sum][i]=sum;
dfs(sum,sum);
zhuanyi();
int io,k,s;
scanf("%d%d%d",&io,&k,&s);
int LAST=0;
for(int i=1;i<=io;i++){
int p0,v0,v,p;
scanf("%d%d",&v0,&p0);
v=(v0+k*LAST-1)%n+1;
p=(p0+k*LAST)%(s+1);
int L=bei(v,p);
LAST=dis[r[L]];
printf("%d\n",LAST);
}
}
}
```
by _maze @ 2020-11-17 20:25:42
@[little_coco](/user/149219) 您多测不清空的吗？两个样例加起来就能把你hack了
by tommy0221 @ 2020-11-17 20:36:31
@[世外明月](/user/123384) 谢谢qwq
by _maze @ 2020-11-17 20:39:35
@[世外明月](/user/123384) 但MLE是什么鬼呀，改了也MLE
by _maze @ 2020-11-17 20:42:36
@[little_coco](/user/149219)
```cpp
#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
inline int read()
{
int x = 0; bool op = false;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar();
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int N = 200010;
const int M = 400010;
const int INF = 1e9;
int n, m, tot1, tot2, pt, q, k, s;
int dis[N], head1[N], to1[M * 2], nxt1[M * 2], edge1[M * 2], val[N * 2];
int f[N * 2], head2[N * 2], to2[N * 4], nxt2[N * 4], mini[N * 2], dp[N * 2][25];
bool vis[N];
struct Node
{
int id, dist;
bool operator < (const Node &tmp) const
{
return dist > tmp.dist;
}
Node(int id = 0, int dist = 0):
id(id), dist(dist){}
};
struct Edge
{
int u, v, w;
bool operator < (const Edge &tmp) const
{
return w > tmp.w;
}
Edge(int u = 0, int v = 0, int w = 0):
u(u), v(v), w(w){}
}e[M];
void addedge1(int u, int v, int w)
{
to1[++tot1] = v;
edge1[tot1] = w;
nxt1[tot1] = head1[u];
head1[u] = tot1;
return ;
}
void addedge2(int u, int v)
{
to2[++tot2] = v;
nxt2[tot2] = head2[u];
head2[u] = tot2;
return ;
}
int find(int x)
{
if(f[x] == x)return x;
return f[x] = find(f[x]);
}
void unionn(int x, int y)
{
int fx = find(x), fy = find(y);
if(fx != fy)f[fy] = fx;
return ;
}
void dijkstra()
{
priority_queue<Node> q;
memset(dis, 0x3f, sizeof(dis));
memset(vis, false, sizeof(vis));
q.push(Node(1, 0)); dis[1] = 0;
while(q.empty() == false)
{
Node cur = q.top(); q.pop();
int u = cur.id;
if(vis[u] == true)continue;
vis[u] = true;
for(int i = head1[u]; i; i = nxt1[i])
{
if(dis[to1[i]] >= dis[u] + edge1[i])
{
dis[to1[i]] = dis[u] + edge1[i];
q.push(Node(to1[i], dis[to1[i]]));
}
}
}
return ;
}
void kruskal()
{
for(int i = 1; i <= n * 2; i++)f[i] = i;
sort(e + 1, e + 1 + m);
for(int i = 1; i <= m; i++)
{
int u = find(e[i].u), v = find(e[i].v);
if(u == v)continue;
pt++;
unionn(pt, u); unionn(pt, v);
val[pt] = e[i].w;
addedge2(pt, u); addedge2(u, pt);
addedge2(pt, v); addedge2(v, pt);
}
return ;
}
void pre(int u, int fa)
{
if(u > n)mini[u] = INF;
else mini[u] = dis[u];
dp[u][0] = fa;
for(int i = 1; i <= 20; i++)
dp[u][i] = dp[dp[u][i - 1]][i - 1];
for(int i = head2[u]; i; i = nxt2[i])
{
if(to2[i] == fa)continue;
pre(to2[i], u);
mini[u] = min(mini[u], mini[to2[i]]);
}
return ;
}
int jump(int u, int p)
{
int now = u;
for(int i = 20; i >= 0; i--)
if(val[dp[now][i]] > p)
now = dp[now][i];
return now;
}
void work()
{
tot1 = tot2 = 0;
memset(head1, 0, sizeof(head1));
memset(head2, 0, sizeof(head2));
memset(val, 0, sizeof(val));
memset(dp, 0, sizeof(dp));
n = read(); m = read();
for(int i = 1; i <= m; i++)
{
int u = read(), v = read(), l = read(), a = read();
addedge1(u, v, l); addedge1(v, u, l);
e[i] = Edge(u, v, a);
}
dijkstra();
pt = n; kruskal();
pre(pt, 0);
q = read(); k = read(); s = read();
int lst = 0;
for(int i = 1; i <= q; i++)
{
int v = read(), p = read();
v = (v + k * lst - 1) % n + 1;
p = (p + k * lst) % (s + 1);
lst = mini[jump(v, p)];
printf("%d\n", lst);
}
}
int main()
{
int t = read();
while(t--)work();
return 0;
}
```
by __gcd @ 2020-11-17 20:53:58
@[一只大头](/user/149192) 过了，但我不知道为什么过的。。。。
by _maze @ 2020-11-17 20:54:47