{"raw_statement":[{"iden":"background","content":"在洛谷上提交本题**不是**交互题，请注意提交方式。\n\n本题测试数据很大，评测可能需要加载 1-2 分钟。\n\n[英文题面](https://www2.ioi-jp.org/camp/2021/2021-sp-tasks/day2/escape_route-en.pdf)。"},{"iden":"statement","content":"IOI 王国使用 Byou（秒）作为时间单位，将一天划分成 $S$ Byou，分别称为时刻 $0,1,\\dotsc,S-1$。\n\nIOI 王国中有 $N$ 个城市和 $M$ 条双向道路，均从 $0$ 开始标号。保证任两个城市之间均连通。第 $i$ 条道路连接城市 $A_i$ 和 $B_i$，需要恰好 $L_i$ Byou 通过。每天的时刻 $C_i$ 后，第 $i$ 条道路将开始进行检查，直到当天结束。\n\nJOI 组织是一个活跃在 IOI 王国中的秘密团体。出于其保密性，成员不能在道路上受到检查。如果其成员想要通过道路 $i$，最晚要在时刻 $C_i-L_i$ 到达这条路的一端。道路的检查不会影响两端的城市。\n\n现在有 $Q$ 名 JOI 组织的成员，从 $0$ 开始标号。第 $j$ 名成员在某天的时刻 $T_j$，要从城市 $U_j$ 出发去城市 $V_j$。成员可以在任意城市内停留任意长的时间。注意这名成员可能会在路上花费一天以上。\n\n请计算每名成员花费的最短时间，精确到 Byou."},{"iden":"input","content":"第一行四个正整数 $N,M,S,Q$。\n\n接下来 $M$ 行，第 $i$ 行四个正整数表示 $A_{i-1},B_{i-1},L_{i-1},C_{i-1}$。\n\n接下来 $Q$ 行，第 $i$ 行三个正整数表示 $U_{i-1},V_{i-1},T_{i-1}$。"},{"iden":"output","content":"输出共 $Q$ 行，第 $i$ 行表示第 $i-1$ 名成员旅行所需的最短时间。"},{"iden":"note","content":"对于 $100\\%$ 的数据，保证：\n\n- $2 \\leq N \\leq 90$。\n- $N-1 \\leq M \\leq \\dfrac{N(N-1)}{2}$。\n- $2 \\leq S \\leq 10^{15}$。\n- $1 \\leq Q \\leq 3 \\times 10^6$。\n- $0 \\leq A_i,B_i \\leq N-1$。\n- $A_i \\neq B_i$。\n- $\\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)$。\n- $1 \\leq L_i \\leq C_i < S$。\n- 从任意城市出发走过一些边后，可以到达任意其他城市。\n- $0\\leq U_j,V_j \\leq N-1$。\n- $U_j \\neq V_j$。\n- $0 \\leq T_j < S$。\n\n有 $5 \\%$ 的分数，满足 $N \\leq 40,Q \\leq 1000$。\n\n另有 $20 \\%$ 的分数，满足 $N \\leq 40,U_j=0$\n\n另有 $10 \\%$ 的分数，满足 $N \\leq 40$。\n\n另有 $35 \\%$ 的分数，满足 $N \\leq 60$。\n\n**建议使用较快的 IO 方式。**"}],"translated_statement":null,"sample_group":[["4 5 20 6\n0 1 3 19\n0 2 2 8\n1 2 4 15\n1 3 5 14\n2 3 1 18\n0 3 5\n0 3 7\n0 3 9\n2 0 6\n3 1 10\n1 2 15","3\n8\n14\n2\n5\n7"],["6 10 100 9\n5 3 4 29\n1 0 6 26\n0 4 2 7\n0 5 18 18\n2 0 79 82\n3 4 35 46\n1 2 15 57\n2 4 3 6\n4 1 21 83\n3 2 47 53\n0 2 63\n0 4 70\n0 4 98\n0 5 25\n0 5 19\n0 4 96\n0 5 2\n0 3 62\n0 3 83","42\n32\n4\n93\n99\n6\n102\n60\n39"],["8 12 1000000000000000 13\n2 0 4451698272827 120985696255786\n6 5 78520421713825 342652131468508\n2 1 185377268405175 382583457603811\n0 4 54350742205838 133614919589507\n7 0 68486247989149 651590905094148\n0 6 85177550834829 299184420663240\n5 2 442329739732459 926608308293721\n3 7 78020232822359 913548478810253\n1 3 267796317244889 687571310475622\n5 4 90590208828121 910324397566584\n5 7 8414633059584 17796117322043\n4 6 45682367792138 204548471584556\n7 2 44779065000162\n3 5 79376234836942\n4 7 305556687070759\n4 3 927935834343174\n5 1 663284649258985\n2 5 967584209777344\n5 2 963749709374595\n7 4 484562389171308\n1 5 446160773830045\n6 4 801452311055604\n3 1 744524289545354\n0 6 467418420721777\n5 6 371181379240653","72937946261976\n929038398222642\n702857945988825\n272921388674172\n580895059624855\n181808439529442\n117602869946965\n569788353034530\n1181546234307589\n244230056736534\n513790925121797\n617759130113052\n674500988551485"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}