```cpp
#include <bits/stdc++.h>
using namespace std;
namespace liuzimingc {
#define int long long
#define pii pair<int, int>
#define endl '\n'
const int N = 8e5 + 5, INF = 1e18;
int T, n, m, a[N], lastans, pos[N]; // >= i 的最后一个位置，最后后缀跑一下
int dis[N];
bool vis[N];
priority_queue<pii> q;
vector<pii> e[N];
vector<int> lsh;
struct edge {
int u, v, w;
} edge[N];
struct persistent_segment_tree {
int root[N], tot, a[N];
struct tree {
int l, r, v;
} t[N << 3];
void build(int &p, int l, int r) {
p = ++tot;
t[p].l = l, t[p].r = r;
if (l == r) {
t[p].v = a[l];
return;
}
int mid = l + r >> 1;
build(t[p].l, l, mid);
build(t[p].r, mid + 1, r);
}
void update(int &p, int pre, int l, int r, int x, int v) {
p = ++tot;
t[p] = t[pre];
if (l == r) {
t[p].v = v;
return;
}
int mid = l + r >> 1;
if (x <= mid) update(t[p].l, t[p].l, l, mid, x, v);
else update(t[p].r, t[p].r, mid + 1, r, x, v);
}
int ask(int p, int l, int r, int x) {
if (l == r) return t[p].v;
int mid = l + r >> 1;
if (x <= mid) return ask(t[p].l, l, mid, x);
else return ask(t[p].r, mid + 1, r, x);
}
} fa, siz, d;
int find(int x, int p) {
int f = fa.ask(fa.root[p], 1, n, x);
return f == x ? x : find(f, p);
}
void merge(int x, int y, int p) {
x = find(x, p), y = find(y, p);
if (x == y) return;
int sizx = siz.ask(siz.root[p], 1, n, x), sizy = siz.ask(siz.root[p], 1, n, y);
int dx = d.ask(d.root[p], 1, n, x), dy = d.ask(d.root[p], 1, n, y);
if (sizx > sizy) swap(x, y);
fa.update(fa.root[p], fa.root[p], 1, n, x, y);
siz.update(siz.root[p], siz.root[p], 1, n, y, sizx + sizy);
d.update(d.root[p], d.root[p], 1, n, y, min(dx, dy));
}
void dijkstra(int s) {
for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = false;
q.push(make_pair(0, s));
dis[s] = 0;
while (q.size()) {
int u = q.top().second; q.pop();
if (vis[u]) continue;
vis[u] = true;
for (const auto &i : e[u]) {
int v = i.first, w = i.second;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
q.push(make_pair(-dis[v], v));
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i <= n; i++) e[i].clear();
lsh.clear();
for (int i = 1; i <= m; i++) {
int u, v, w, a;
cin >> u >> v >> w >> a;
edge[i].u = u, edge[i].v = v, edge[i].w = a;
lsh.push_back(a);
e[u].push_back(make_pair(v, w));
e[v].push_back(make_pair(u, w));
}
lsh.push_back(-1);
sort(lsh.begin(), lsh.end());
lsh.resize(unique(lsh.begin(), lsh.end()) - lsh.begin());
dijkstra(1);
sort(edge + 1, edge + 1 + m, [](auto a, auto b){ return a.w > b.w; });
fa.tot = siz.tot = d.tot = 0;
for (int i = 1; i <= n; i++) fa.a[i] = i, siz.a[i] = 1, d.a[i] = dis[i];
fa.build(fa.root[0], 1, n);
siz.build(siz.root[0], 1, n);
d.build(d.root[0], 1, n);
for (int i = 1; i <= m; i++) {
fa.root[i] = fa.root[i - 1];
siz.root[i] = siz.root[i - 1];
d.root[i] = d.root[i - 1];
merge(edge[i].u, edge[i].v, i);
edge[i].w = lower_bound(lsh.begin(), lsh.end(), edge[i].w) - lsh.begin();
pos[edge[i].w] = i;
}
pos[lsh.size()] = 0;
for (int i = lsh.size() - 1; i; i--) pos[i] = max(pos[i], pos[i + 1]);
int q, k, s;
cin >> q >> k >> s;
lastans = 0;
for (int case_id = 1; case_id <= q; case_id++) {
int v, p;
cin >> v >> p;
v = (v + k * lastans - 1) % n + 1;
p = (p + k * lastans) % (s + 1);
if (lsh.back() <= p) {
// cerr << case_id << endl;
cout << (lastans = dis[v]) << endl;
continue;
}
int x = upper_bound(lsh.begin(), lsh.end(), p) - lsh.begin();
x = pos[x];
int f = fa.ask(fa.root[x], 1, n, v);
cout << (lastans = d.ask(d.root[x], 1, n, f)) << endl;
}
}
return 0;
}
#undef int
}
int main() {
liuzimingc::main();
return 0;
}
```
by liuzimingc @ 2024-08-15 15:04:45