#include "escape_route.h"
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#define int long long
#define INF (1LL << 60)
using namespace std;
const int N = 91;
struct edge{
int to, l, c;
};
vector<edge> G[N];
int S;
int norm(int tx){
tx %= S;
if(tx < 0) tx += S;
return tx;
}
vector<pair<int, int>> Ti[N][N], Sc[N][N];
int D[N][N], La[N][N];
void add_data(int x, int y, int tx, int ty){
if(tx <= -(INF >> 1) || ty >= (INF >> 1)) return;
int rtx = norm(tx);
int rty = ty + rtx - tx;
int tot = rty - rtx;
Ti[x][y].push_back({rtx, tot});
}
vector<int> from(int x, int t){
vector<int> d(N, -INF); d[x] = t;
priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq;
pq.push({t, x});
while(!pq.empty()){
auto [t, v] = pq.top(); pq.pop();
if(d[v] != t) continue;
for(auto [to, l, c] : G[v]){
int tp = norm(t), nt;
if(tp > c){ // back to c
nt = t - (tp - c) - l;
}else if(tp >= l){ // ok
nt = t - l;
}else{ // no last day
nt = -INF;
}
if(nt > d[to]){
d[to] = nt;
pq.push({nt, to});
}
}
}
return d;
}
vector<int> to(int x, int t, bool allow_midnight){
vector<int> d(N, INF); d[x] = t;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({t, x});
while(!pq.empty()){
auto [t, v] = pq.top(); pq.pop();
if(d[v] != t) continue;
for(auto [to, l, c] : G[v]){
int tp = norm(t), nt;
if(tp > c - l){ // next day
nt = allow_midnight ? t + (S - tp) + l : INF;
}else{ // ok
nt = t + l;
}
if(nt < d[to]){
d[to] = nt;
pq.push({nt, to});
}
}
}
return d;
}
vector<int> calculate_necessary_time(int32_t N, int32_t M, int S, int32_t Q,
vector<int32_t> A, vector<int32_t> B, vector<int> L, vector<int> C,
vector<int32_t> U, vector<int32_t> V, vector<int> T) {
::S = S;
for(int i = 0; i < M; i++){
G[A[i]].push_back({B[i], L[i], C[i]});
G[B[i]].push_back({A[i], L[i], C[i]});
}
for(int i = 0; i < M; i++){
vector<int> d1, d2;
d1 = from(A[i], C[i] - L[i]);
d2 = to(B[i], C[i], false);
for(int x = 0; x < N; x++){
for(int y = 0; y < N; y++){
add_data(x, y, d1[x], d2[y]);
}
}
d1 = from(B[i], C[i] - L[i]);
d2 = to(A[i], C[i], false);
for(int x = 0; x < N; x++){
for(int y = 0; y < N; y++){
add_data(x, y, d1[x], d2[y]);
}
}
}
for(int i = 0; i < N; i++){
vector<int> d = to(i, 0, true);
for(int j = 0; j < N; j++){
D[i][j] = d[j];
}
}
for(int u = 0; u < N; u++){
for(int v = 0; v < N; v++){
vector<pair<int, int>> vp;
sort(Ti[u][v].begin(), Ti[u][v].end());
for(auto [tx, tot] : Ti[u][v]){
while(!vp.empty() && vp.back().second >= tot) vp.pop_back();
if(!vp.empty() && vp.back().first == tx) continue;
vp.push_back({tx, tot});
}
Ti[u][v] = vp;
}
}
for(int u = 0; u < N; u++){
for(int v = 0; v < N; v++){
if(u != v) La[u][v] = Ti[u][v].empty() ? -1 : (--Ti[u][v].end())->first;
else La[u][v] = S;
}
}
for(int x = 0; x < N; x++){
for(int y = 0; y < N; y++){
for(int z = 0; z < N; z++){
Sc[x][z].push_back({La[x][y], D[y][z]});
}
}
}
for(int u = 0; u < N; u++){
for(int v = 0; v < N; v++){
vector<pair<int, int>> vp;
sort(Sc[u][v].begin(), Sc[u][v].end());
for(auto [tx, tot] : Sc[u][v]){
while(!vp.empty() && vp.back().second >= tot) vp.pop_back();
if(!vp.empty() && vp.back().first == tx) continue;
vp.push_back({tx, tot});
}
Sc[u][v] = vp;
}
}
vector<int> ans(Q, INF);
for(int i = 0; i < Q; i++){
auto ptr = lower_bound(Ti[U[i]][V[i]].begin(), Ti[U[i]][V[i]].end(), pair<int, int>{T[i], 0});
if(ptr != Ti[U[i]][V[i]].end()){
ans[i] = min(ans[i], ptr->second);
}
ptr = lower_bound(Sc[U[i]][V[i]].begin(), Sc[U[i]][V[i]].end(), pair<int, int>{T[i], 0});
if(ptr != Sc[U[i]][V[i]].end()){
ans[i] = min(ans[i], ptr->second + S - T[i]);
}
}
return ans;
}
