#include <bits/stdc++.h>
#include "escape_route.h"
using i64 = long long;
#ifdef DEBUG
#include "../../debug.h"
#else
#define debug(...) void(23)
#endif
constexpr i64 inf = i64(1E18);
template<typename T>
bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<typename T>
bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
std::vector<i64> calculate_necessary_time(
int N, int M, i64 S, int Q, std::vector<int> A, std::vector<int> B,
std::vector<i64> L, std::vector<i64> C, std::vector<int> U,
std::vector<int> V, std::vector<i64> T) {
std::vector<i64> res(Q, inf);
std::vector<std::vector<int>> adj(N);
for (int i = 0; i < M; ++i) {
adj[A[i]].emplace_back(i);
adj[B[i]].emplace_back(i);
}
auto work_forward = [&](int start, i64 t) -> std::vector<i64> {
std::vector<int> vis(N);
std::vector<i64> dis(N, inf);
dis[start] = t;
for (int i = 0; i < N; ++i) {
int v = -1;
for (int j = 0; j < N; ++j) {
if (vis[j]) {
continue;
}
if (v == -1 || dis[v] > dis[j]) {
v = j;
}
}
vis[v] = true;
for (auto e : adj[v]) {
int u = A[e] ^ B[e] ^ v;
i64 nd = dis[v] + L[e];
if (dis[v] % S > C[e] - L[e]) {
nd += S - dis[v] % S;
}
chmin(dis[u], nd);
}
}
return dis;
};
auto work_backward = [&](int start, i64 t) -> std::vector<i64> {
std::vector<int> vis(N);
std::vector<i64> dis(N, -inf);
dis[start] = t;
for (int i = 0; i < N; ++i) {
int v = -1;
for (int j = 0; j < N; ++j) {
if (vis[j]) {
continue;
}
if (v == -1 || dis[v] < dis[j]) {
v = j;
}
}
vis[v] = true;
for (auto e : adj[v]) {
int u = A[e] ^ B[e] ^ v;
i64 nd = std::min(dis[v], C[e]) - L[e];
chmax(dis[u], nd);
}
}
return dis;
};
std::vector<std::vector<i64>> fw_dist(N);
std::vector<std::vector<i64>> bk_dist(N);
for (int i = 0; i < N; ++i) {
fw_dist[i] = work_forward(i, 0);
bk_dist[i] = work_backward(i, S);
debug(fw_dist[i]);
debug(bk_dist[i]);
}
std::vector<std::vector<std::pair<i64, std::vector<i64>>>> mind(N, std::vector<std::pair<i64, std::vector<i64>>>(2 * M));
for (int i = 0; i < M; ++i) {
for (int rep = 0; rep < 2; ++rep) {
std::vector<i64> max_time = work_backward(A[i], C[i] - L[i]);
std::vector<i64> arrival = work_forward(B[i], C[i]);
debug(max_time);
debug(arrival);
for (int j = 0; j < N; ++j) {
mind[j][2 * i + rep] = {max_time[j], arrival};
}
std::swap(A[i], B[i]);
}
}
std::vector<std::vector<std::vector<i64>>> minarrivals(N, std::vector<std::vector<i64>>(2 * M + 1, std::vector<i64>(N, inf)));
for (int i = 0; i < N; ++i) {
std::sort(mind[i].begin(), mind[i].end(), [&](auto lhs, auto rhs) -> bool {
return lhs.first < rhs.first;
});
for (int j = 2 * M - 1; j >= 0; --j) {
for (int k = 0; k < N; ++k) {
if (mind[i][j].second[k] <= S) {
minarrivals[i][j][k] = mind[i][j].second[k] - mind[i][j].first;
}
chmin(minarrivals[i][j][k], minarrivals[i][j + 1][k]);
}
debug(mind[i][j].first, minarrivals[i][j]);
}
debug();
}
for (int i = 0; i < Q; ++i) {
int lo = 0, hi = 2 * M;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (mind[U[i]][mid].first >= T[i]) {
hi = mid;
} else {
lo = mid + 1;
}
}
debug(minarrivals[U[i]][lo][V[i]]);
chmin(res[i], minarrivals[U[i]][lo][V[i]]);
for (int j = 0; j < N; ++j) {
if (bk_dist[j][U[i]] >= T[i]) {
chmin(res[i], S - T[i] + fw_dist[j][V[i]]);
}
}
}
return res;
}
