Background

Submitting this problem on Luogu is not interactive. Please pay attention to the submission method.

The testdata for this problem is very large, and the judge may need 1–2 minutes to load.

English statement.

Problem Description

The IOI Kingdom uses Byou (seconds) as the unit of time, and divides one day into $S$ Byou, called times $0,1,\dotsc,S-1$.

In the IOI Kingdom, there are $N$ cities and $M$ undirected roads, all numbered starting from $0$. It is guaranteed that every pair of cities is connected. The $i$-th road connects cities $A_i$ and $B_i$, and it takes exactly $L_i$ Byou to traverse. Every day, after time $C_i$, the $i$-th road starts being inspected until the end of the day.

The JOI Organization is a secret group active in the IOI Kingdom. For confidentiality, its members must not be inspected on roads. If a member wants to traverse road $i$, they must arrive at one endpoint of this road no later than time $C_i-L_i$. Inspections on a road do not affect the cities at its endpoints.

Now there are $Q$ members of the JOI Organization, numbered starting from $0$. On some day, member $j$ starts from city $U_j$ at time $T_j$ and wants to go to city $V_j$. A member may stay in any city for any amount of time. Note that this member may spend more than one day on the trip.

For each member, compute the shortest time they need, accurate to Byou.

Input Format

The first line contains four positive integers $N,M,S,Q$.

The next $M$ lines describe the roads. Line $i$ contains four positive integers $A_{i-1},B_{i-1},L_{i-1},C_{i-1}$.

The next $Q$ lines describe the queries. Line $i$ contains three positive integers $U_{i-1},V_{i-1},T_{i-1}$.

Output Format

Output $Q$ lines. Line $i$ contains the shortest travel time required for member $i-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

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

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

Hint

Constraints for $100\%$ of the data:

• $2 \leq N \leq 90$.
• $N-1 \leq M \leq \dfrac{N(N-1)}{2}$.
• $2 \leq S \leq 10^{15}$.
• $1 \leq Q \leq 3 \times 10^6$.
• $0 \leq A_i,B_i \leq N-1$.
• $A_i \neq B_i$.
• $\forall i,j \in [0,M-1]$，if $i \neq j$, then $(A_i,B_i) \neq (A_j,B_j)$ and $(A_i,B_i) \neq (B_j,A_j)$.
• $1 \leq L_i \leq C_i < S$.
• Starting from any city and traversing some edges, it is possible to reach any other city.
• $0\leq U_j,V_j \leq N-1$.
• $U_j \neq V_j$.
• $0 \leq T_j < S$.

For $5\%$ of the score: $N \leq 40, Q \leq 1000$.

For another $20\%$ of the score: $N \leq 40, U_j=0$.

For another $10\%$ of the score: $N \leq 40$.

For another $35\%$ of the score: $N \leq 60$.

It is recommended to use fast I/O.

Translated by ChatGPT 5