在 IOI 王国中，他们使用“秒”（Byou）作为时间单位。IOI 王国的一天被划分为 $S$ 个时间单位。一天开始后 $x$ 秒（$0 \le x < S$）的时刻被称为时间 $x$。IOI 王国包含 $N$ 个城市，编号从 $0$ 到 $N - 1$。有 $M$ 条道路连接这些城市，编号从 $0$ 到 $M - 1$。你可以通过经过若干条道路从任意城市前往其他任何城市。道路 $i$（$0 \le i \le M - 1$）双向连接城市 $A_i$ 和城市 $B_i$。通过道路 $i$ 从一端到达另一端需要 $L_i$ 秒。每天，道路 $i$ 都会在时间 $C_i$ 到一天结束时进行严格的安全检查。
JOI 集团是 IOI 王国中的秘密教派之一。由于这是一个秘密教派，JOI 集团成员的身份是严格保密的。这意味着 JOI 集团的成员不应遇到每天进行的严格安全检查。因此，如果一名 JOI 集团成员想要通过道路 $i$，该成员必须在时间 $x$ 从城市 $A_i$ 或城市 $B_i$ 出发，并在时间 $x + L_i$ 到达另一个城市，其中需满足 $0 \le x \le C_i - L_i$。由于城市中不进行严格安全检查，当道路 $i$ 进行严格安全检查时，JOI 集团成员可以待在城市 $A_i$ 或城市 $B_i$ 中。
JOI 集团共有 $Q$ 名成员，编号从 $0$ 到 $Q - 1$。成员 $j$（$0 \le j \le Q - 1$）在某天的 $T_j$ 时刻从城市 $U_j$ 出发，开始前往城市 $V_j$。成员可以在途中的城市停留一段时间。成员 $j$ 到达城市 $V_j$ 可能需要多天。
请编写一个程序，在给定 IOI 王国的城市和道路信息、严格安全检查信息以及 JOI 集团成员信息的情况下，计算每名成员 $j$（$0 \le j \le Q - 1$）从城市 $U_j$ 到达城市 $V_j$ 所需的最短时间。
实现细节
为了加快输入和输出速度，本题使用评测器进行评测。
你需要提交一个文件。提交的文件名为 escape_route.cpp。它应实现以下函数。程序应使用预处理指令 #include 包含 escape_route.h。
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$ 是 IOI 王国的城市数量。
- 参数 $M$ 是 IOI 王国的道路数量。
- 参数 $S$ 表示 IOI 王国的一天有 $S$ 秒。
- 参数 $Q$ 是 JOI 集团的成员数量。
- 参数 $A, B, L, C$ 是长度为 $M$ 的数组。它们表示道路 $i$（$0 \le i \le M - 1$）连接城市 $A[i]$ 和城市 $B[i]$，通过道路 $i$ 需要 $L[i]$ 秒，且道路 $i$ 的严格安全检查在时间 $C[i]$ 开始。
- 参数 $U, V, T$ 是长度为 $Q$ 的数组。它们表示成员 $j$（$0 \le j \le Q - 1$）在时间 $T[j]$ 从城市 $U[j]$ 出发，开始前往城市 $V[j]$。
- 该函数应返回一个长度为 $Q$ 的
long long类型数组answer。这意味着对于每个 $0 \le j \le Q - 1$，成员 $j$ 从城市 $U[j]$ 到达城市 $V[j]$ 所需的最短时间为answer[j]秒。
重要提示
- 你的程序不得使用标准输入和标准输出。你的程序不得以任何方式与其他文件通信。但是，你的程序可以将调试信息输出到标准错误。
- 评测器不检查输入格式。如果输入格式不正确，评测器的行为无法保证。
- 如果
calculate_necessary_time返回的数组长度与 $Q$ 不同，或者数组包含负整数，则评测器的行为无法保证。
编译与测试
你可以从竞赛网页下载包含评测器的压缩包来测试你的程序。压缩包中还包含一个示例源文件。
评测器文件为 grader.cpp。为了测试你的程序，请将 grader.cpp、escape_route.cpp 和 escape_route.h 放在同一目录下，并运行以下命令来编译你的程序：
g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp escape_route.cpp
编译成功后，将生成可执行文件 grader。
在本题中，竞赛网页上提供的评测器与 CMS 系统中实际使用的评测器相同。
数据范围
- $2 \le N \le 90$
- $N - 1 \le M \le \frac{N(N - 1)}{2}$
- $2 \le S \le 1\,000\,000\,000\,000\,000 = 10^{15}$
- $1 \le Q \le 3\,000\,000$
- $0 \le A_i \le N - 1$ ($0 \le i \le M - 1$)
- $0 \le B_i \le N - 1$ ($0 \le i \le M - 1$)
- $A_i \neq B_i$ ($0 \le i \le M - 1$)
- $(A_i, B_i) \neq (A_k, B_k), (A_i, B_i) \neq (B_k, A_k)$ ($0 \le i < k \le M - 1$)
- $1 \le L_i < S$ ($0 \le i \le M - 1$)
- $L_i \le C_i < S$ ($0 \le i \le M - 1$)
- 你可以通过经过若干条道路从任意城市前往其他任何城市。
- $0 \le U_j \le N - 1$ ($0 \le j \le Q - 1$)
- $0 \le V_j \le N - 1$ ($0 \le j \le Q - 1$)
- $U_j \neq V_j$ ($0 \le j \le Q - 1$)
- $0 \le T_j < S$ ($0 \le j \le Q - 1$)
子任务
- (5 分) $N \le 40, Q \le 1\,000$
- (20 分) $N \le 40, U_j = 0$ ($0 \le j \le Q - 1$)
- (10 分) $N \le 40$
- (35 分) $N \le 60$
- (30 分) 无附加限制
样例
样例 1
输入：
4 5 20 6 0 1 3 19 0 2 2 8 1 2 4 15 1 3 5 14 2 3 1 18 0 3 5 0 3 7 0 3 9 2 0 6 3 1 10 1 2 15
输出：
3 8 14 2 5 7
样例 2
输入：
6 10 100 9 5 3 4 29 1 0 6 26 0 4 2 7 0 5 18 18 2 0 79 82 3 4 35 46 1 2 15 57 2 4 3 6 4 1 21 83 3 2 47 53 0 2 63 0 4 70 0 4 98 0 5 25 0 5 19 0 4 96 0 5 2 0 3 62 0 3 83
输出：
42 32 4 93 99 6 102 60 39
样例 3
输入：
8 12 1000000000000000 13 2 0 4451698272827 120985696255786 6 5 78520421713825 342652131468508 2 1 185377268405175 382583457603811 0 4 54350742205838 133614919589507 7 0 68486247989149 651590905094148 0 6 85177550834829 299184420663240 5 2 442329739732459 926608308293721 3 7 78020232822359 913548478810253 1 3 267796317244889 687571310475622 5 4 90590208828121 910324397566584 5 7 8414633059584 17796117322043 4 6 45682367792138 204548471584556 7 2 44779065000162 3 5 79376234836942 4 7 305556687070759 4 3 927935834343174 5 1 663284649258985 2 5 967584209777344 5 2 963749709374595 7 4 484562389171308 1 5 446160773830045 6 4 801452311055604 3 1 744524289545354 0 6 467418420721777 5 6 371181379240653
输出：
72937946261976 929038398222642 702857945988825 272921388674172 580895059624855 181808439529442 117602869946965 569788353034530 1181546234307589 244230056736534 513790925121797 617759130113052 674500988551485