1. 题目

传送门=￣ω￣=

2. 题解

Emmm。。。

先说下惨痛经历：同步赛的时候一眼过去就是可持久化并查集。。。然后打了大概 80 分钟，过了 4 个样例然后被卡 SPFA 和并查集启发式合并大概又打了 40 分钟。。。就过了 5 个样例，信心满满卡了点常就交了。。。

最后发下来 100 分变 65 分。。。WA 了。。。

什么鬼？？？QAQ

仔细一看。。。哇 QvQ 代码当中，钻出来一个光头！

我把 last_ans 作为局部变量了，然后忘记清零了。。。

Woc。。。我还是跳楼自杀吧。。。

好了下面开始说正事。。。

首先对于离线我们可以想到一个很简单的解法：

• 最短路求出每个点到 1 号点的最短距离
• 把询问从大到小排序
• 从大到小加边，并查集维护每个联通快内的点到 1 号点的距离中的最小值
• 对于一个询问，如果所有海拔大于它的边都加上了就直接查询问中的点所在的联通块内到点 1 的最小距离，输出即可。

知道这个暴力简单的解法以后，正解也就很好想了。

因为题目强制在线，所以我们并不能排序，但我们依然可以很暴力地搞个可持久化并查集把状态存下来，然后每个询问去找对应的并查集历史版本，然后按照上面离线的那种思路查询即可。

此题思维难度很低，代码难度较高 QwQ

可持久化并查集启发式合并，弄个主席树就行了。节点数 $=(2\times 10^5 + 2\times 4\times 10 ^5)\times \lceil log_2(2\times 10 ^5) + 1\rceil = 1.9\times 10^7$

还有一个小技巧可以省空间，就是启发式合并需要存储并查集集合高度，那个东西没必要放到主席树里，因为查询的时候并不需要用到并查集高度这一属性，直接把并查集高度放在一个普通数组里就行了。

代码：

#include <bits/stdc++.h>

#define NS (200005)
#define MS (400005)
#define FIR first
#define SEC second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct graph
{
    int head[NS], to[MS << 1], nxt[MS << 1], w[MS << 1], sz;
    void init() {memset(head, -1, sizeof(head)), sz = 0;}
    graph() {init();}
    void push(int a, int b, int c)
    {
        nxt[sz] = head[a], to[sz] = b, w[sz] = c, head[a] = sz++;
    }
    int operator [] (const int a) const {return to[a];}
} g;

struct edge
{
    int u, v, l, a;
    edge() {u = v = l = a = 0;}
    edge(int x, int y, int p, int q)
    {
        u = x, v = y, l = p, a = q;
    }
    bool operator > (const edge oth) const
    {
        if (a == oth.a)
        {
            if (l == oth.l)
            {
                if (u == oth.u) return v > oth.v;
                return u > oth.u;
            }
            return l > oth.l;
        }
        return a > oth.a;
    }
} E[MS];

int T, n, m, h[MS], dis[NS], He[NS];

priority_queue<PII, vector<PII>, greater<PII> > pq;

void dij()
{
    memset(dis, 127, sizeof(dis)), pq.push(PII(0, 1)); PII F;
    while (!pq.empty())
    {
        F = pq.top(), pq.pop();
        if (F.FIR >= dis[F.SEC]) continue;
        dis[F.SEC] = F.FIR;
        for (int i = g.head[F.SEC]; ~i; i = g.nxt[i])
            if (dis[g[i]] > dis[F.SEC] + g.w[i])
                pq.push(PII(dis[F.SEC] + g.w[i], g[i]));
    }
}

/**CMT**/

struct N {int x, y, l, r;} e[19000005];

int root[MS], sz;

void Build(int l, int r, int& a)
{
    a = sz++;
    if (l == r) {e[a].x = l, e[a].y = dis[l], e[a].l = e[a].r = 0; return;}
    int mid = (l + r) >> 1;
    Build(l, mid, e[a].l), Build(mid + 1, r, e[a].r);
}

PII Query(int x, int a)
{
    int L = 1, R = n, Mid;
    while (L < R)
    {
        Mid = (L + R) >> 1;
        if (x <= Mid) a = e[a].l, R = Mid;
        else a = e[a].r, L = Mid + 1;
    }
    return PII(e[a].x, e[a].y);
}

void Updatex(int x, int d, int L, int R, int& p, int q)
{
    p = sz++, e[p] = e[q];
    if (L == R) {e[p].x = d; return;}
    int Mid = (L + R) >> 1;
    if (x <= Mid) Updatex(x, d, L, Mid, e[p].l, e[q].l);
    else Updatex(x, d, Mid + 1, R, e[p].r, e[q].r);
}

void Updatey(int x, int d, int L, int R, int& p, int q)
{
    p = sz++, e[p] = e[q];
    if (L == R) {e[p].y = d; return;}
    int Mid = (L + R) >> 1;
    if (x <= Mid) Updatey(x, d, L, Mid, e[p].l, e[q].l);
    else Updatey(x, d, Mid + 1, R, e[p].r, e[q].r);
}

/**CMT**/

PII findf(int a, int h)
{
    PII tmp = Query(a, root[h]);
    if (tmp.FIR == a) return tmp;
    return findf(tmp.FIR, h);
}

int main(int argc, char const* argv[])
{
    IN(T);
    while (T--)
    {
        IN(n), IN(m), g.init(), sz = 0;
        for (int i = 1; i <= n; i += 1) He[i] = 1;
        for (int i = 1, u, v, a, b; i <= m; i += 1)
        {
            IN(u), IN(v), IN(a), IN(b);
            E[i] = edge(u, v, a, b), g.push(u, v, a), g.push(v, u, a);
        }
        sort(E + 1, E + 1 + m, greater<edge>());
        for (int i = 1; i <= m; i += 1) h[i] = E[i].a;
        dij(), Build(1, n, root[0]); PII r1, r2;
        for (int i = 1; i <= m; i += 1)
        {
            root[i] = root[i - 1];
            r1 = findf(E[i].u, i - 1), r2 = findf(E[i].v, i - 1);
            if (r1.FIR != r2.FIR)
            {
                if (He[r1.FIR] > He[r2.FIR]) swap(r1, r2);
                else if (He[r1.FIR] == He[r2.FIR]) He[r2.FIR]++;
                Updatex(r1.FIR, r2.FIR, 1, n, root[i], root[i]);
                Updatey(r2.FIR, min(r1.SEC, r2.SEC), 1, n, root[i], root[i]);
            }
        }
        int q, k, s, lst = 0;
        IN(q), IN(k), IN(s);
        for (int C = 1, v, p; C <= q; C += 1)
        {
            IN(v), IN(p);
            v = ((LL)v + k * lst - 1) % n + 1;
            p = ((LL)p + k * lst) % (s + 1);
            p = lower_bound(h + 1, h + 1 + m, p, greater<int>()) - h - 1;
            r1 = findf(v, p), lst = r1.SEC, printf("%d\n", lst);
        }
    }
    return 0;
}