#include <bits/stdc++.h>
using namespace std;
const int64_t inf = 1e17;
vector<long long> calculate_necessary_time(int N, int M, long long S, int Q, vector<int> A, vector<int> B,
vector<long long> L, vector<long long> C, vector<int> U,
vector<int> V, vector<long long> T) {
#define int int64_t
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i < M; ++i) {
adj[A[i]].push_back({B[i], i});
adj[B[i]].push_back({A[i], i});
}
auto solve_from_0 = [&](int u, int t) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({t, u});
vector<bool> vis(N);
vector<int> ans(N);
while (!pq.empty()) {
auto [t, u] = pq.top();
pq.pop();
if (vis[u]) {
continue;
}
vis[u] = true;
ans[u] = t;
for (auto &[i, idx] : adj[u]) {
int l = L[idx];
if ((t % S) <= C[idx] - l) {
pq.push({t + l, i});
} else {
pq.push({(t / S) * S + S + l, i});
}
}
}
return ans;
};
vector ans_from_0(N, vector<int>(N));
for (int i = 0; i < N; ++i) {
ans_from_0[i] = solve_from_0(i, 0);
}
// auto sssp = [&](int u) {
// priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// pq.push({0, u});
// vector<int> ans(N);
// vector<bool> vis(N);
// while (!pq.empty()) {
// auto [d, u] = pq.top();
// pq.pop();
// if (vis[u]) {
// continue;
// }
// vis[u] = true;
// ans[u] = d;
// for (auto &[i, idx] : adj[u]) {
// int l = L[idx];
// pq.push({d + l, i});
// }
// }
// return ans;
// };
auto solve = [&](int u, int v, int t) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({t, u});
vector<bool> vis(N);
int ans = inf;
while (!pq.empty()) {
auto [t, u] = pq.top();
pq.pop();
if (vis[u]) {
continue;
}
vis[u] = true;
ans = min(ans, int64_t(ans_from_0[u][v] + S));
if (u == v) {
return min(ans, t);
}
for (auto &[i, idx] : adj[u]) {
int l = L[idx];
if (t + l <= C[idx]) {
pq.push({t + l, i});
}
}
}
return ans;
};
vector<long long> ans(Q);
// lets maintain a vector dist[][] that stores the *current* shortest distance
// lets also sort queries so that queries with the highest T[i] come first: likely nothing can reach that's why
vector<vector<int>> dist(N, vector<int>(N, inf));
for (int i = 0; i < N; ++i) {
dist[i][i] = 0;
}
auto add_edge = [&](int a, int b, int l) {
// cout << "activating edge " << a << ' ' << b << ' ' << l << endl;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
dist[i][j] = min(dist[i][j], dist[i][a] + l + dist[b][j]);
}
}
};
vector<vector<pair<int, int>>> edge_queue(N);
for (int i = 0; i < M; ++i) {
edge_queue[A[i]].push_back({C[i] - L[i], i});
edge_queue[B[i]].push_back({C[i] - L[i], i});
}
for (auto &i : edge_queue) { // back has biggest, pop from back
sort(i.begin(), i.end());
}
vector<int> ord(Q);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) { return T[i] > T[j]; });
for (int &i : ord) {
// U[i], V[i], T[i] is the query
// dist(0, u)
for (int node = 0; node < N; ++node) {
while (!edge_queue[node].empty() && edge_queue[node].back().first >= T[i] + dist[U[i]][node]) {
int idx = edge_queue[node].back().second;
add_edge(node, A[idx] + B[idx] - node, L[idx]);
edge_queue[node].pop_back();
}
}
int cur_ans = T[i] + dist[U[i]][V[i]];
for (int node = 0; node < N; ++node) {
if (dist[U[i]][node] != inf) {
cur_ans = min(cur_ans, ans_from_0[node][V[i]] + int64_t(S));
}
}
// cout << "cur_ans = " << cur_ans << '\n';
ans[i] = cur_ans - T[i];
}
// for (int i = 0; i < Q; ++i) {
// ans[i] = solve(U[i], V[i], T[i]) - T[i];
// }
#undef int
return ans;
}
