Time‐Travel in IOI Kingdom

The citizens of IOI Kingdom use the unit Byou to measure time. One day is divided into \(S\) Byou. The \(x\)th Byou (\(0\le x<S\)) is called time \(x\).

The kingdom contains \(N\) cities (numbered \(0\) to \(N-1\)) and \(M\) bidirectional roads (numbered \(0\) to \(M-1\)). Each road \(i\) connects city \(A_i\) and city \(B_i\) and takes \(L_i\) Byou to traverse. Every day, road \(i\) is inspected from time \(C_i\) until the end of the day. In order for a member of the secret JOI group to use road \(i\) without being caught in an inspection, the member must enter the road strictly before time \(C_i - L_i\) on that day.

There are \(Q\) JOI group members. The \(j\)th member (numbered \(0\) to \(Q-1\)) wishes to travel from city \(U_j\) to city \(V_j\) starting at time \(T_j\) (on some day). Members may wait arbitrarily long at any city. Note that a journey may span several days. Your task is to compute, for each member, the minimum total time (in Byou) required to complete their journey.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The input is given as follows:

S N M
A0 B0 L0 C0
A1 B1 L1 C1
... 
AM-1 BM-1 LM-1 CM-1
Q
U0 V0 T0
U1 V1 T1
...
UQ-1 VQ-1 TQ-1

All numbers are integers. The cities are numbered \(0\) to \(N-1\). For each road \(i\), the road connects city \(A_i\) and city \(B_i\), takes \(L_i\) Byou to traverse, and is inspected from time \(C_i\) until the end of the day. A JOI member can only start traversing road \(i\) if the departure time (the local time in the day) is strictly less than \(C_i - L_i\).

outputFormat

For each query, output the minimum total time (in Byou) required to complete the journey. If there are multiple queries, output the answers in the order of input, one per line.

sample

10 3 2
0 1 3 8
1 2 4 9
1
0 2 0

7