#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> calculate_necessary_time(int n, int m, ll S, int q, vector<int> A, vector<int> B, vector<ll> L, vector<ll> C,
vector<int> U, vector<int> V, vector<ll> T) {
constexpr ll inf = 3e18;
vector<ll> answer(q, inf);
vector<vector<int>> queries(n);
for (int i = 0; i < q; ++i) {
queries[U[i]].push_back(i);
}
A.resize(2 * m), B.resize(2 * m), L.resize(2 * m), C.resize(2 * m);
for (int i = 0; i < m; ++i) {
A[i + m] = B[i], B[i + m] = A[i];
C[i + m] = C[i], L[i + m] = L[i];
}
m *= 2;
vector<vector<int>> adj(n);
for (int i = 0; i < m; ++i) {
adj[A[i]].push_back(i);
}
auto dijkstra = [&](int source, ll s) -> vector<ll> {
vector<ll> dist(n, inf);
dist[source] = s;
vector<bool> used(n);
for (int _ = 0; _ < n; ++_) {
int v = -1;
for (int i = 0; i < n; ++i) {
if (!used[i] && (v == -1 || dist[i] < dist[v])) {
v = i;
}
}
used[v] = true;
for (int i : adj[v]) {
int to = B[i];
ll d = L[i] + (dist[v] % S <= C[i] - L[i] ? dist[v] : (dist[v] / S + 1) * S);
if (dist[to] > d) {
dist[to] = d;
}
}
}
for (int i = 0; i < n; ++i) {
dist[i] = dist[i] - s;
}
return dist;
};
vector dist0(n, vector<ll>(n));
vector dp(m, vector<ll>(n));
for (int i = 0; i < n; ++i) {
dist0[i] = dijkstra(i, 0);
}
for (int e = 0; e < m; ++e) {
dp[e] = dijkstra(A[e], C[e] - L[e]);
for (int to = 0; to < n; ++to) {
if (C[e] - L[e] + dp[e][to] >= S) {
dp[e][to] = inf;
}
}
}
for (int i = 0; i < n; ++i) {
sort(adj[i].begin(), adj[i].end(), [&](int x, int y) {
return C[x] - L[x] > C[y] - L[y];
});
};
for (int i = 0; i < n; ++i) {
sort(queries[i].begin(), queries[i].end(), [&](int x, int y) {
return T[x] > T[y];
});
int k = 0;
vector<int> id(n);
vector<ll> d(m, inf);
d[i] = 0;
while (true) {
pair<ll, int> best{-1, -1};
for (int x = 0; x < n; ++x) {
if (id[x] < adj[x].size()) {
int e = adj[x][id[x]];
best = max(best, {C[e] - L[e] - d[x], x});
}
}
while (k < queries[i].size() && T[queries[i][k]] > best.first) {
int j = queries[i][k++];
answer[j] = min(answer[j], d[V[j]]);
for (int x = 0; x < n; ++x) {
if (T[j] + d[x] < S) {
answer[j] = min(answer[j], S - T[j] + dist0[x][V[j]]);
}
}
}
if (best.first == -1) {
break;
}
int x = best.second;
int e = adj[x][id[x]++];
for (int to = 0; to < n; ++to) {
d[to] = min(d[to], d[x] + dp[e][to]);
}
}
}
return answer;
}
