#include <bits/stdc++.h>
using namespace std;
struct node {
    long long u, v, w, h;
}a[4000000 + 10];
struct com {
    long long name, val;
    friend bool operator < (com x, com y) {
        return x.val < y.val;
    }
};
priority_queue <com> q;
com dis[2000000 + 10];
bool vis[2000000 + 10];
long long  cnt = 0, fa[2000000 + 10], anc[30][2000000 + 10];
long long last[2000000 + 10], n, m, kal[2000000 + 10]; 
vector <pair<long long , long long> > head[8000000 + 10];
long long inline found(long long x) {
    while (fa[x] != x)
        x = fa[x] = fa[fa[x]];
    return x;
}
void inline add (long long x, long long y, long long z) {
    head[x].push_back(make_pair(y, z));
}
void inline add2 (long long i, long long x, long long y) {
    x = found(x); y = found(y); cnt ++;
    fa[x] = fa[y] = fa[cnt] = cnt;
    kal[cnt] = a[i].h;
    add(cnt, x, 0); add(cnt, y, 0);
}
void inline best (long long x) {
    long long len = head[x].size();  last[x] = dis[x].val;
    if(x <= n) return ;
    for(register int i = 0; i < len; i ++) {
        long long f = head[x][i].first;
        anc[f][0] = x;  best(f);
        last[x] = min(last[x], last[f]);
    }
}
bool cmp (node x, node y) {return x.h > y.h;}
int main ()  {
    long long T, lastans = 0; scanf ("%lld" ,&T);
    while (T --) {
        memset(last, 0, sizeof(last));
        memset(vis, false, sizeof(vis));
        memset(dis, 0x3f, sizeof(dis));
        scanf("%lld%lld", &n, &m);
        for ( register int i = 1; i <= m; i ++)  {
            scanf("%lld%lld%lld%lld", &a[i].u, &a[i].v, &a[i].w, &a[i].h);
            add(a[i].u, a[i].v, i); add(a[i].v, a[i].u, i);
        }
        long long len = head[1].size(); dis[1].val = 0; vis[1] = true;
        for(register int i = 1; i <= n; i ++) dis[i].name = i;
        for(register int i = 0; i < len; i ++) {
            long long  x = head[1][i].first, y = head[1][i].second;
            dis[x].val = a[y].w; q.push(dis[a[y].v]);
        }
        printf("\n");
        while(!q.empty()) { //cout<<1;
            com top = q.top();
            if(vis[top.name] || dis[top.name].val != top.val)
                {q.pop(); continue;}
            len = head[top.name].size(); vis[top.name] = true;
            for(register int i = 0 ; i < len; i ++) {
                long long x = head[top.name][i].first, y = head[top.name][i].second;
                if(dis[x].val > dis[top.name].val + a[y].w) {
                    dis[x].val = dis[top.name].val + a[y].w;
                    if(!vis[x])  q.push(dis[x]);
                }
            }
        } 

        sort(a + 1, a + m + 1, cmp); cnt = n;
        for(register int i = 1; i <= n + m; i ++) fa[i] = i;
        for(register int i = 1; i <= m; i ++)
            if(found(a[i].u) != found(a[i].v))
                add2(i, a[i].u, a[i].v);
        best(cnt);
//      for(register int i=  1; i <= cnt; i ++)
//          cout<<last[i]<<endl;
        for(register int i = 1; (1 << i) <= cnt; i ++)
            for(register int j = 1; j <= cnt ; j++)
                anc[j][i] = anc[anc[j][i -1]][i-1];
        long long Q, K, S; scanf("%lld%lld%lld", &Q, &K, &S);
        for(register int i = 1 ; i <= Q; i ++) {
            long long v0, p0; scanf("%lld%lld", &v0, &p0);
            v0 = (v0 + K * lastans - 1) % n + 1;
            p0 = (p0 + K * lastans) % (S + 1);
            for(register int j = 22; j >= 0; j --)
                if(anc[v0][j] && kal[anc[v0][j]] > p0)
                    v0 = anc[v0][j];
//          cout<<v0<<endl;
            printf("%lld\n", last[v0]); lastans = last[v0];
        }
    }
}

RT 代码如上