#include "escape_route.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
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) {
vector<ll> K(M);
for(ll i=0; i<M; ++i) K[i] = C[i] - L[i];
vector<ll> ans(Q);
vector<vector<vector<ll>>> queries(N, vector<vector<ll>>(N));
for(ll i=0; i<Q; ++i) {
queries[U[i]][V[i]].push_back(i);
}
vector<vector<pair<ll, ll>>> g(N);
for(ll i=0; i<M; ++i) {
g[A[i]].push_back({B[i], i});
g[B[i]].push_back({A[i], i});
}
ll inf = 1e18;
auto dijkstra_min = [&](ll s, ll val) {
vector<ll> dist(N, inf), vis(N,0);
dist[s] = val;
while(1) {
pair<ll, ll> best = {inf,0};
for(ll i=0; i<N; ++i) if(!vis[i]) best = min(best, {dist[i], i});
if(best.first == inf) break;
auto[dv,v] = best;
vis[v] = 1;
for(auto[u,k] : g[v]) {
ll w = L[k];
ll t = dv%S;
if(t > K[k]) w += S-t;
if(dist[u] > dist[v] + w) {
dist[u] = dist[v] + w;
}
}
}
return dist;
};
auto dijkstra_max = [&](ll s, ll val) {
vector<ll> dist(N, -1), vis(N,0);
dist[s] = val;
while(1) {
pair<ll, ll> best = {-1,0};
for(ll i=0; i<N; ++i) if(!vis[i]) best = max(best, {dist[i], i});
if(best.first == -1) break;
auto[dv,v] = best;
vis[v] = 1;
for(auto[u,k] : g[v]) {
ll nd = min(K[k], dv-L[k]);
if(dist[u] < nd) {
dist[u] = nd;
}
}
}
return dist;
};
vector<vector<ll>> day0(N);
for(ll i=0; i<N; ++i) day0[i] = dijkstra_max(i, S-1);
vector<vector<ll>> dist(N);
for(ll i=0; i<N; ++i) dist[i] = dijkstra_min(i, 0);
vector<vector<ll>> DX(2*M), DY(2*M);
for(int i=0; i<M; ++i) {
DX[2*i] = dijkstra_max(A[i], K[i]);
DX[2*i+1] = dijkstra_max(B[i], K[i]);
DY[2*i] = dijkstra_min(B[i], C[i]);
DY[2*i+1] = dijkstra_min(A[i], C[i]);
}
vector<int> edges;
for(int i=0; i<2*M; ++i) edges.push_back(i);
for(ll s=0; s<N; ++s) {
sort(edges.begin(), edges.end(), [&](int i, int j) {
return DX[i][s] > DX[j][s];
});
for(ll u=0; u<N; ++u) {
sort(queries[s][u].begin(), queries[s][u].end(), [&](int i, int j) { return T[i] > T[j]; });
ll best = inf;
int cnt = 0;
for(auto idx : queries[s][u]) {
while(cnt < edges.size()) {
int i = edges[cnt];
if(DX[i][s] >= T[idx]) {
best = min(best, DY[i][u] - DX[i][s]);
cnt++;
} else break;
}
if(T[idx]==0) {
ans[idx] = dist[s][u];
continue;
}
ans[idx] = inf;
if(day0[u][s] < T[idx]) {
for(int i=0; i<N; ++i) if(day0[i][s] >= T[idx]) ans[idx] = min(ans[idx], S + dist[i][u]);
ans[idx] -= T[idx];
} else {
// cout << idx << ": " << s << " -> " << u << " " << T[idx] << "\n";
ans[idx] = best;
}
}
}
}
return ans;
}
