#include <bits/stdc++.h>
using namespace std;
const int64_t inf = 1e18;
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 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));
auto add_edge = [&](int a, int b, int l) {
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());
}
auto process = [&](const vector<int> &ord) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
dist[i][j] = i == j ? 0 : inf;
}
}
auto edge_queue = Edge_queue;
for (const int &i : ord) {
// U[i], V[i], T[i] is the query
// dist(0, u)
int changed = 1;
while (changed) {
changed = 0;
for (int node = 0; node < N; ++node) {
while (!edge_queue[node].empty() && edge_queue[node].back().first >= T[i] + dist[U[i]][node]) {
changed = 1;
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));
}
}
ans[i] = cur_ans - T[i];
}
};
vector<vector<int>> ord(N);
for (int i = 0; i < Q; ++i) {
ord[U[i]].push_back(i);
}
for (auto &i : ord) {
sort(i.begin(), i.end(), [&](int i, int j) { return T[i] > T[j]; });
process(i);
}
#undef int
return ans;
}
