#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 91;
const int MAXM = 4010;
const ll inf = 4e18;
vector<pair<int, int>> adj[MAXN];
bool vis[MAXN];
vector<pair<ll, int>> qv[MAXN][MAXN];
ll rdist[MAXM][2][MAXN], fdist[MAXM][2][MAXN], mtsd[MAXN][MAXN], d0[MAXN][MAXN];
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){
for (int i = 0; i < M; i++){
int a = A[i], b = B[i];
adj[a].push_back({b, i}); adj[b].push_back({a, i});
}
for (int i = 0; i < M; i++)
for (int k = 0; k < 2; k++)
for (int x = 0; x < N; x++){
rdist[i][k][x] = -1; fdist[i][k][x] = inf;
}
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++){
mtsd[i][j] = -1; d0[i][j] = inf;
}
for (int i = 0; i < M; i++){
int a = A[i], b = B[i]; ll l = L[i], c = C[i];
for (int k = 0; k < 2; k++){
memset(vis, 0, sizeof(vis));
rdist[i][k][a] = c - l;
while (1){
int cx = -1; ll cv = -1;
for (int x = 0; x < N; x++)
if (!vis[x] && rdist[i][k][x] > cv){
cx = x; cv = rdist[i][k][x];
}
if (cx == -1) break;
vis[cx] = 1;
for (auto [nn, ne] : adj[cx]){
if (vis[nn]) continue;
ll nd = min(C[ne], cv) - L[ne];
if (nd > rdist[i][k][nn]) rdist[i][k][nn] = nd;
}
}
memset(vis, 0, sizeof(vis));
fdist[i][k][b] = c;
while (1){
int cx = -1; ll cv = inf;
for (int x = 0; x < N; x++)
if (!vis[x] && fdist[i][k][x] < cv){
cx = x; cv = fdist[i][k][x];
}
if (cx == -1) break;
vis[cx] = 1;
for (auto [nn, ne] : adj[cx]){
if (vis[nn]) continue;
ll nd = cv + L[ne];
if (nd < min(C[ne] + 1, fdist[i][k][nn])) fdist[i][k][nn] = nd;
}
}
swap(a, b);
}
}
for (int i = 0; i < N; i++){
memset(vis, 0, sizeof(vis));
mtsd[i][i] = S - 1;
while (1){
int cx = -1; ll cv = -1;
for (int x = 0; x < N; x++)
if (!vis[x] && mtsd[i][x] > cv){
cx = x; cv = mtsd[i][x];
}
if (cx == -1) break;
vis[cx] = 1;
for (auto [nn, ne] : adj[cx]){
if (vis[nn]) continue;
ll nd = min(C[ne], cv) - L[ne];
if (nd > mtsd[i][nn]) mtsd[i][nn] = nd;
}
}
memset(vis, 0, sizeof(vis));
d0[i][i] = 0;
while (1){
int cx = -1; ll cv = inf;
for (int x = 0; x < N; x++)
if (!vis[x] && d0[i][x] < cv){
cx = x; cv = d0[i][x];
}
if (cx == -1) break;
vis[cx] = 1;
ll ct = cv % S, ndy = cv - ct + S;
for (auto [nn, ne] : adj[cx]){
if (vis[nn]) continue;
ll nd = (ct <= C[ne] - L[ne] ? cv : ndy) + L[ne];
if (nd < d0[i][nn]) d0[i][nn] = nd;
}
}
}
for (int i = 0; i < Q; i++) qv[U[i]][V[i]].push_back({T[i], i});
vector<ll> av(Q);
for (int u = 0; u < N; u++){
vector<tuple<ll, int, int>> eord;
for (int i = 0; i < M; i++)
for (int k = 0; k < 2; k++)
if (rdist[i][k][u] != -1)
eord.push_back({rdist[i][k][u], i, k});
sort(eord.begin(), eord.end());
vector<pair<ll, int>> rbde;
for (int i = 0; i < N; i++)
if (mtsd[u][i] != inf)
rbde.push_back({mtsd[i][u], i});
sort(rbde.begin(), rbde.end());
for (int v = 0; v < N; v++){
sort(qv[u][v].begin(), qv[u][v].end(), greater<pair<ll, int>>());
int eid = eord.size() - 1, did = rbde.size() - 1;
ll ans = inf, ansd = inf;
for (auto [tm, id] : qv[u][v]){
for (; eid >= 0 && get<0>(eord[eid]) >= tm; eid--){
ll st; int i, k; tie(st, i, k) = eord[eid];
ans = min(ans, fdist[i][k][v] - st);
}
for (; did >= 0 && rbde[did].first >= tm; did--){
ll st; int x; tie(st, x) = rbde[did];
ansd = min(ansd, d0[x][v]);
}
av[id] = min(ans, S - tm + ansd);
}
}
}
return av;
}
