背景

在洛谷上提交本题不是交互题，请注意提交方式。

本题测试数据很大，评测可能需要加载 1-2 分钟。

英文题面。

题目描述

IOI 王国使用 Byou（秒）作为时间单位，将一天划分成 $S$ Byou，分别称为时刻 $0,1,\dotsc,S-1$。

IOI 王国中有 $N$ 个城市和 $M$ 条双向道路，均从 $0$ 开始标号。保证任两个城市之间均连通。第 $i$ 条道路连接城市 $A_i$ 和 $B_i$，需要恰好 $L_i$ Byou 通过。每天的时刻 $C_i$ 后，第 $i$ 条道路将开始进行检查，直到当天结束。

JOI 组织是一个活跃在 IOI 王国中的秘密团体。出于其保密性，成员不能在道路上受到检查。如果其成员想要通过道路 $i$，最晚要在时刻 $C_i-L_i$ 到达这条路的一端。道路的检查不会影响两端的城市。

现在有 $Q$ 名 JOI 组织的成员，从 $0$ 开始标号。第 $j$ 名成员在某天的时刻 $T_j$，要从城市 $U_j$ 出发去城市 $V_j$。成员可以在任意城市内停留任意长的时间。注意这名成员可能会在路上花费一天以上。

请计算每名成员花费的最短时间，精确到 Byou.

输入格式

第一行四个正整数 $N,M,S,Q$。

接下来 $M$ 行，第 $i$ 行四个正整数表示 $A_{i-1},B_{i-1},L_{i-1},C_{i-1}$。

接下来 $Q$ 行，第 $i$ 行三个正整数表示 $U_{i-1},V_{i-1},T_{i-1}$。

输出格式

输出共 $Q$ 行，第 $i$ 行表示第 $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

提示

对于 $100\%$ 的数据，保证：

• $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]$，若 $i \neq j$，则有 $(A_i,B_i) \neq (A_j,B_j),(A_i,B_i) \neq (B_j,A_j)$。
• $1 \leq L_i \leq C_i < S$。
• 从任意城市出发走过一些边后，可以到达任意其他城市。
• $0\leq U_j,V_j \leq N-1$。
• $U_j \neq V_j$。
• $0 \leq T_j < S$。

有 $5 \%$ 的分数，满足 $N \leq 40,Q \leq 1000$。

另有 $20 \%$ 的分数，满足 $N \leq 40,U_j=0$

另有 $10 \%$ 的分数，满足 $N \leq 40$。

另有 $35 \%$ 的分数，满足 $N \leq 60$。

建议使用较快的 IO 方式。