题目背景

本题不是交互题，请注意提交方式。

英文题面。

题目描述

IOI 王国的国民使用 Byou 作为时间单位。

IOI 王国中，一天被划分为 $S$ Byou，其中第 $x$ 个 Byou($0\leq x < S$) 被称为时刻 $x$。

IOI 王国中有 $N$ 个城市（标号 $0\sim N-1$）和 $M$ 条双向道路（标号 $0 \sim M-1$），你可以通过道路从一个城市移动到另一个城市。第 $i$ 条道路直接连接着城市 $A_i$ 和 $B_i$，通过这条道路需要 $L_i$ Byou。每天，从时刻 $C_i$ 开始要对第 $i$ 条道路进行检查，直到这一天结束。

JOI 集团是 IOI 王国中的一个秘密组织，出于其保密性，JOI 集团的成员不应该在道路上受到检查，这意味着如果 JOI 王国的成员如果想要通过道路 $i$，那么他必须在时刻 $C_i-L_i$ 之前踏上这条路。

现在有 $Q$ 名 JOI 集团的成员（标号 $0 \sim Q-1$），第 $j$ 名成员在某一天的时刻 $T_j$ 想要从城市 $U_j$ 出发旅行去城市 $V_j$。成员可以在城市内停留任意长的时间。这名成员可能要花费多天才能到达城市 $V_j$。

现要求计算每个成员完成旅行所需要的最少时间。

输入格式

第一行四个正整数 $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$ 名成员旅行所需的最少时间。

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 (0 \leq i \leq M-1)$。
• $A_i \ne B_i(0 \leq i \leq M-1)$。
• $\forall i,j \in [0,M-1]$，若 $i \ne j$，则有 $(A_i,B_i) \ne (A_j,B_j),(A_i,B_i) \ne (B_j,A_j)$。。
• $1 \leq L_i \leq C_i < S$。
• 你可以从某个城市经过若干条道路到达任意另一个城市。
• $0\leq U_j,V_j \leq N-1(0 \leq J \leq Q-1)$。
• $U-j \ne 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 方式。