rt，TLE on 10-14&17-20，在用第10个点调试时通过输出运行时间发现主要开销在dfs函数，而且dfs没有死循环，但是单次调用耗时出奇的大（在输出调试的情况下每几千层就要一秒，删去调试代码差不多在十三万层程序就卡死了），不知道是哪里的锅

代码：

#include <bits/stdc++.h>
#define maxn 400010
#define maxm 800010
#define maxjump 20
#define writeln(X) write(X), putchar('\n')
using namespace std;
template < typename T >
inline void read(T &X)
{
    X = 0; bool f = false; char ch = getchar();
    while (!isdigit(ch)) {f |= ch == '-'; ch = getchar();}
    while (isdigit(ch)) {X = (X * 10) + (ch ^ 48); ch = getchar();}
    X = f ? -X : X;
}
template < typename T >
inline void write(T X)
{
    if (X == 0) {putchar('0'); return;}
    if (X < 0) {putchar('-'); X = -X;}
    static int num[21], cnt = 0;
    while (X) {num[++cnt] = X % 10; X /= 10;}
    while (cnt) putchar(num[cnt--] ^ 48);
}
struct disside {int v, w, next;} dissidelist[maxm << 1];
int dissidecnt, head[maxn];
inline void buildside(const int &u, const int &v, const int &w) {dissidelist[++dissidecnt] = {v, w, head[u]}; head[u] = dissidecnt;}
int n, m;
struct heapnode
{
    int id, val;
    heapnode (const int &_id = 0, const int &_val = 0) : id(_id), val(_val) {}
    bool operator < (const heapnode &b) const {return this->val > b.val;}
};
int dis[maxn];
priority_queue < heapnode > q;
//关于SPFA,它死了
inline void dijk()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0; q.emplace(1, 0);
    while(!q.empty())
    {
        int x = q.top().id, w = q.top().val;
        q.pop();
        if (w > dis[x]) continue;
        for (int i = head[x]; i; i = dissidelist[i].next)
        {
            int to = dissidelist[i].v, d = dis[x] + dissidelist[i].w;
            if (d < dis[to]) q.emplace(to, d), dis[to] = d;
        }
    }
}
struct side
{
    int u, v, w;
    bool operator < (const side &b) const {return this->w > b.w;}
}sidelist[maxm];
int fa[maxn << 1], val[maxn << 1];
int Krucnt;
int getfa(const int &x)
{
    if (fa[x] == x) return x;
    return fa[x] = getfa(fa[x]);
}
vector < int > Kruside[maxn];
void Kru()
{
    Krucnt = n;
    for (int i = 1; i <= (n << 1) - 1; ++i) fa[i] = i, Kruside[i].clear();
    sort(sidelist + 1, sidelist + m + 1);
    for (int i = 1; i <= m; ++i)
    {
        int u = sidelist[i].u, v = sidelist[i].v, w = sidelist[i].w;
        u = getfa(u), v = getfa(v);
        if (u != v)
        {
            ++Krucnt;
            fa[u] = Krucnt, fa[v] = Krucnt;
            val[Krucnt] = w;
            Kruside[Krucnt].emplace_back(u); Kruside[Krucnt].emplace_back(v);
        }
        if (Krucnt == (n << 1) - 1) break;
    }
}
int mindis[maxn << 1];
int ST[maxn << 1][maxjump + 5];
void dfs(const int &x)
{
    if (x <= n) {mindis[x] = dis[x]; return;}
    mindis[x] = 0x3f3f3f3f;
    for (int to : Kruside[x])
    {
        dfs(to);
        mindis[x] = min(mindis[x], mindis[to]);
        ST[to][0] = x;
    }
}
int main()
{
    freopen("P4768.in", "r", stdin);
    freopen("P4768.out", "w", stdout);
    int T;
    read(T);
    while (T--)
    {
        dissidecnt = 0; memset(head, 0, sizeof(head));
        read(n); read(m);
        for (int i = 1; i <= m; ++i)
        {
            int u, v, l, a;
            read(u); read(v); read(l); read(a);
            buildside(u, v, l); buildside(v, u, l);
            sidelist[i] = {u, v, a};
        }
        dijk();
        // for (int i = 1; i <= n; ++i) cerr << dis[i] << endl;
        Kru();
        dfs(Krucnt);
        ST[Krucnt][0] = Krucnt;
        for (int j = 1; j <= maxjump; ++j)
            for (int i = 1; i <= n; ++i)
                ST[i][j] = ST[ST[i][j - 1]][j - 1];
        int q, k, s, lastans = 0;
        read(q); read(k); read(s);
        for (int i = 1; i <= q; ++i)
        {
            int v, p;
            read(v); read(p);
            v = ((v + k * lastans - 1) % n) + 1, p = (p + k * lastans) % (s + 1);
            for (int j = maxjump; j >= 0; --j)
                while (val[ST[v][j]] > p && v != Krucnt) v = ST[v][j];
            lastans = mindis[v];
            writeln(lastans);
        }
    }
}