在 IOI 王国，时间的计量单位是 Byou，一天被划为 $S$ 单位时间。每一天经过 $x(0\leq x\lt S)$ 时间后的时刻被称为时刻 $x$。

IOI 王国有 $N$ 座城市，编号从 $0$ 到 $N-1$。城市间有 $M$ 条双向道路，第 $i(0\leq i\lt M)$ 条道路连接城市 $A_i$ 和 $B_i$，并且从时刻 $C_i$ 开始直到当天末尾这条路将进行安全检查，并且通过这条路需要 $L_i$ 单位时间。任意两个城市之间均可通过道路到达。

JOI 组织是 IOI 王国的秘密组织之一，为了保密，他们的成员不希望遇到安全检查。因此，如果 JOI 组织的成员想要通过某条路 $i$，他出发的时间为 $x$，则他到达另一端的时间为 $x+L_i$，因此他需要保证 $0\leq x\leq C_i-L_i$。不过安全检查并不会涉及到城市，因此即使当一条道路处于检查时期，JOI 组织的成员仍然可以停留或通过两端的城市。

JOI 组织有 $Q$ 个成员，编号从 $0$ 到 $Q-1$。第 $j$ 个成员会从某天的时刻 $j$ 从城市 $U_j$ 出发，动身前往城市 $V_j$，他想知道他最少需要多久才能到达。在路途中，可以停留在某个城市以等待检查结束。

请你求出每个成员需要的最短时间。

输入格式

第一行四个整数 $N,M,S,Q$，分别表示城市数，道路数，每天时刻数，询问个数。

接下来 $M$ 行，每行四个整数 $A_i,B_i,L_i,C_i$ 表示一条道路。

接下来 $Q$ 行，每行三个整数 $U_i,V_i,T_i$ 表示一次询问。

输出格式

$Q$ 行，每行一个整数表示对于第 $i$ 个询问，最少需要几单位时间才能到达。具体的，设出发时间为时刻 $T_i$，最早到达时间为 $x$ 天后的时刻 $T'_i$，你需要输出 $xS+T'_i-T_i$。

样例一

input

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

output

3
8
14
2
5
7

explanation

这组数据满足 $\text{Subtask}~1,3,4,5$ 的限制。

在时刻 $5$，成员 $0$ 开始从城市 $0$ 前往城市 $3$，他将花费 $3$ 单位时间，具体的：

1. 经过道路 $1$，在时刻 $7$ 到达城市 $2$。
2. 经过道路 $4$，在时刻 $8$ 到达城市 $3$。

在时刻 $7$，成员 $1$ 同样开始从城市 $0$ 前往城市 $3$，他将花费 $8$ 单位时间，具体的：

1. 经过道路 $0$，在时刻 $10$ 到达城市 $1$。
2. 经过道路 $2$，在时刻 $14$ 到达城市 $2$。
3. 经过道路 $4$，在时刻 $15$ 到达城市 $3$。

在时刻 $9$，成员 $2$ 同样开始从城市 $0$ 前往城市 $3$，他将花费 $14$ 单位时间，具体的：

1. 在原地停留直至第二天。
2. 经过道路 $1$，在时刻 $2$ 到达城市 $2$。
3. 经过道路 $4$，在时刻 $3$ 到达城市 $3$。

样例二

input

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

output

42
32
4
93
99
6
102
60
39

explanation

这组数据满足所有子任务的限制。

样例三

见附件下载中的 ex_route3.in 和 ex_route3.ans。

这组数据满足 $\text{Subtask}~1,3,4,5$ 的限制。

数据范围与提示

对于所有数据，保证 $2\leq N\leq 90, N-1\leq M\leq \frac{N(N-1)}{2}, 2\leq S\leq 10^{15},1\leq Q\leq 3\times 10^6, 0\leq A_i,B_i\lt N,1\leq L_i\leq C_i\lt S, 0\leq U_i,V_i\lt N, U_i\neq V_i, 0\leq T_i\lt S$。

对于所有数据，保证图联通，且不存在自环重边。

$\text{Subtask 1(5 points)}~N\leq 40,Q\leq 1000$。

$\text{Subtask 2(20 points)}~N\leq 40,U_i=0$。

$\text{Subtask 3(10 points)}~N\leq 40$。

$\text{Subtask 4(35 points)}~N\leq 60$。

$\text{Subtask 5(30 points)}$ 无特殊限制。

在下发文件中，提供了一份 sample.cpp 来提供快速输入输出模板，注意如果你选择使用这份模板，你不应当使用其他包括 scanf,printf,cin,cout 在内的输入输出方式。你可以在 main 函数开始时调用 Init() 来获取输入，并在计算出答案后，保存至 ans 数组并调用 Output() 以输出答案。

时间限制：$\texttt{9s}$

空间限制：$\texttt{2GB}$