#include "escape_route.h"
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#define ll long long
using namespace std;
vector <array<ll, 4>> query;
ll adjid[90];
vector <array<ll, 3>> adj[90];
array <ll, 3> par_edge[90];
vector <array<ll, 3>> tree_edge[90][2];
vector <array<ll, 2>> queryb[90][90];
vector <array<ll, 3>> querya[90];
ll dist[90], X[90], fullday[90][90], reachable[90][90];
priority_queue <array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
priority_queue <array<ll, 2>> rpq;
ll n, q, s;
vector <ll> F;
std::vector<long long> calculate_necessary_time(
int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B,
std::vector<long long> L, std::vector<long long> C, std::vector<int> U,
std::vector<int> V, std::vector<long long> T) {
n = N, q = Q, s = S;
F.resize(q);
for (int i=0; i<M; ++i) {
adj[A[i]].push_back({B[i], C[i]-L[i], L[i]});
adj[B[i]].push_back({A[i], C[i]-L[i], L[i]});
}
for (int i=0; i<N; ++i) {
for (int j=0; j<N; ++j) dist[j] = 1e18, X[j] = -1e18;
pq.push({0, i, 0});
dist[i] = 0, X[i] = s-1;
while (!pq.empty()) {
auto [w, u, t] = pq.top();
pq.pop();
if (dist[u] != w) continue;
for (auto [v, lim, len] : adj[u]) {
if (t <= lim && dist[v] > w+len) {
dist[v] = w+len;
pq.push({dist[v], v, t+len});
}
else if (t > lim && dist[v] > w+s-t+len) {
dist[v] = w+s-t+len;
pq.push({dist[v], v, len});
}
}
}
for (int j=0; j<N; ++j) fullday[i][j] = dist[j];
rpq.push({s-1, i});
while (!rpq.empty()) {
auto [w, u] = rpq.top();
rpq.pop();
if (X[u] != w) continue;
reachable[u][i] = X[u];
for (auto [v, lim, len] : adj[u]) {
if (X[v] < min(lim, X[u]-len)) {
X[v] = min(lim, X[u]-len);
rpq.push({X[v], v});
}
}
}
sort(adj[i].begin(), adj[i].end(), [](auto a, auto b) {
return a[1] < b[1];
});
}
for (int i=0; i<q; ++i) query.push_back({U[i], V[i], T[i], i});
sort(query.begin(), query.end(), [](auto a, auto b) {
return a[2] > b[2];
});
for (int i=0; i<q; ++i) {
if (reachable[query[i][0]][query[i][1]] >= query[i][2]) querya[query[i][0]].push_back({query[i][1], query[i][2], query[i][3]});
else queryb[query[i][0]][query[i][1]].push_back({query[i][2], query[i][3]});
}
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
vector <array<ll, 2>> cur;
for (int k=0; k<n; ++k) {
if (reachable[i][k] >= 0) cur.push_back({reachable[i][k], fullday[k][j]});
}
ll f = 1e18;
sort(cur.begin(), cur.end());
for (auto [t, id] : queryb[i][j]) {
while (!cur.empty() && cur.back()[0] >= t) {
f = min(f, cur.back()[1]);
cur.pop_back();
}
F[id] = f+S-t;
}
}
}
for (int i=0; i<n; ++i) {
ll p = S-1;
reverse(querya[i].begin(), querya[i].end());
for (int j=0; j<n; ++j) adjid[j] = adj[j].size()-1;
while (!querya[i].empty()) {
ll newp = -1;
for (int j=0; j<n; ++j) {
dist[j] = 1e18, par_edge[j] = {-1, -1, -1};
swap(tree_edge[j][0], tree_edge[j][1]);
tree_edge[j][1].clear();
}
dist[i] = p;
pq.push({p, i, 0});
while (!pq.empty()) {
auto [w, u, t] = pq.top();
pq.pop();
if (dist[u] != w) continue;
if (par_edge[u][0] != -1) tree_edge[par_edge[u][0]][1].push_back({u, par_edge[u][1], par_edge[u][2]});
while (adjid[u] >= 0 && adj[u][adjid[u]][1] >= dist[u]) {
tree_edge[u][0].push_back(adj[u][adjid[u]]);
--adjid[u];
}
if (adjid[u] >= 0) newp = max(newp, p-dist[u]+adj[u][adjid[u]][1]);
for (auto [v, lim, len] : tree_edge[u][0]) {
if (dist[v] > w+len) {
dist[v] = w+len;
par_edge[v] = {u, lim, len};
pq.push({dist[v], v, 0});
}
}
}
while (!querya[i].empty() && newp < querya[i].back()[1] && querya[i].back()[1] <= p) {
F[querya[i].back()[2]] = dist[querya[i].back()[0]]-p;
querya[i].pop_back();
}
if (newp == -1) break;
p = newp;
}
}
return F;
}
