没有用 Kruskal 重构树 a。直接在最大生成树上倍增，#10之后的都 WA 了，求调。

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define mr make_pair
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 5, M = 4e5 + 5;
int t, n, maxd, m, q, s, k, fa[N][20], mhei[N][20];
ll dis[N], mdis[N][20], lst;
bool vis[N];

struct Ed{
    int u, v, h;
    ll l;
}e[M];
bool cmp(Ed x, Ed y) {
    return x.h > y.h;
}

vector <pil> G[N];

struct DSU{
    int fa[N];
    void init() {
        for (int i = 1; i <= n; ++i) fa[i] = i;
        return ;
    }
    int getroot(int x) {
        if(fa[x] == x) return x;
        return fa[x] = getroot(fa[x]);
    }
    void merge(int x, int y) {
        // x = getroot(x), y = getroot(y);
        fa[x] = y; return ;
    }
}D;

priority_queue <pli, vector<pli>, greater<pli> > pq;
void Dijkstra() {
    while(!pq.empty()) pq.pop();
    fill(vis, vis + n + 1, 0);
    fill(dis, dis + n + 1, 1e17);
    dis[1] = 0; pq.push(mr(0, 1));
    while(!pq.empty()) {
        int u = pq.top().se; pq.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for (int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i].fi; ll w = G[u][i].se;
            if(dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.push(mr(dis[v], v));
            }
        }
    }
    return ;
}

vector <pii> T[N];
void dfs(int u, int ff, int h) {
    fa[u][0] = ff, mhei[u][0] = h, mdis[u][0] = min(dis[u], dis[ff]);
    for (int i = 0; i < T[u].size(); ++i) {
        pii e = T[u][i];
        if(e.fi == ff) continue;
        dfs(e.fi, u, e.se);
    }
    return ;
}

void Tsukinaga() {
    for (int j = 1; j <= maxd; ++j) {
        for (int i = 1; i <= n; ++i) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
            mhei[i][j] = min(mhei[i][j - 1], mhei[fa[i][j - 1]][j - 1]);
            mdis[i][j] = min(mdis[i][j - 1], mdis[fa[i][j - 1]][j - 1]);
        }
    }
    return ;
}

void Kruskal() {
    D.init(); maxd = log2(n);
    sort(e + 1, e + m + 1, cmp);
    int rinne = 0;
    for (int i = 1; i <= m; ++i) {
        if(rinne == n - 1) break;
        int u = D.getroot(e[i].u), v = D.getroot(e[i].v);
        if(u == v) continue;
        rinne++; D.fa[u] = v;
        T[e[i].u].push_back(mr(e[i].v, e[i].h));
        T[e[i].v].push_back(mr(e[i].u, e[i].h));
    }
    dfs(1, 1, 0x3f3f3f3f);
    Tsukinaga();
    return ;
}

ll query(int st, int lim) {
    ll ans = dis[st];
    // cout << mhei[st][1] << "\n";
    for (int i = maxd; i >= 0; --i) {
        if(mhei[st][i] > lim) {            
            ans = min(ans, mdis[st][i]);
            st = fa[st][i];
        }
    }
    return ans;
}

void solve() {
    memset(fa, 0, sizeof(fa));
    memset(mdis, 0, sizeof(mdis));
    memset(mhei, 0, sizeof(mhei));
    lst = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= n; ++i) {
        T[i].clear(), G[i].clear();
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d %lld %d", &e[i].u, &e[i].v, &e[i].l, &e[i].h);
        G[e[i].u].push_back(mr(e[i].v, e[i].l));
        G[e[i].v].push_back(mr(e[i].u, e[i].l));
    }
    Dijkstra();
    Kruskal();
    // for (int i = 1; i <= n; ++i) cout << dis[i] << "\n";
    scanf("%d %d %d", &q, &k, &s);
    for (int i = 1; i <= q; ++i) {
        ll v, p; scanf("%lld %lld", &v, &p);
        v = 1ll * (v + 1ll * k * lst - 1) % n + 1;
        p = 1ll * (p + 1ll * k * lst) % (s + 1);
        // cout << v << ' ' << p << "\n";
        lst = query(v, p);
        printf("%lld\n", lst);
    }
    return ;
}

int main() {
    scanf("%d", &t);
    while(t--) solve();
    return 0;
}