시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
9 초 2048 MB 4 3 2 100.000%

## 문제

In IOI Kingdom, they use Byou as the unit of time. A day in IOI Kingdom is divided into S units of time. The moment x Byous (0 ≤ x < S) after the beginning of a day is called time x. The IOI Kingdom consists of N cities, numbered from 0 to N − 1. There are M roads connecting cities, numbered from 0 to M − 1. You can travel from any city to any other city by passing through some of the roads. The road i (0 ≤ i ≤ M −1) connects the city Ai and the city Bi bidirectionally. It takes Li Byous to pass through the road i from an endpoint to the other endpoint. Every day, a strict security inspection is performed on the road i from time Ci to the end of the day.

JOI Group is one of the secret sects in IOI Kingdom. Since it is a secret sect, the members of JOI Group is strictly confidential. This means members of JOI Group should not encounter a strict security inspection performed every day. Therefore, if a member of JOI Group wants to pass through the road i, the member should depart from either the city Ai or the city Bi at time x and arrive at the other city at time x + Li for some 0 ≤ x ≤ Ci − Li. Since a strict security inspection is not performed in the cities, a member of JOI Group may be at in either the city Ai or the city Bi when a strict security inspection is performed on the road i.

There are Q members in JOI Group, numbered from 0 to Q − 1. The member j (0 ≤ j ≤ Q − 1) departs from the city Uj at time Tj on some day and starts traveling to the city Vj. Members are allowed to stay in cities on the way for a while. It may take multiple days for the member j to arrive at the city Vj.

Write a program which, given the information of the cities and the roads of IOI Kingdom, the information of strict security inspections, and the information of the members of JOI Group, calculates for each j (0 ≤ j ≤ Q − 1) the minimum amount of time required for the member j to travel from the city Uj to the city Vj.

## 구현

You need to submit one file. The name of the file you submit is escape_route.cpp. It should implement the following function. The program should include escape_route.h using the preprocessing directive #include.

• std::vector<long long> calculate_necessary_time( int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B, std::vector<long long> L, std::vector<long long> C, std::vector<int> U, std::vector<int> V, std::vector<long long> T)
This function is called exactly once for each test case.
• The parameter N is the number of cities in IOI Kingdom.
• The parameter M is the number of roads in IOI Kingdom.
• The parameter S means a day in IOI Kingdom is S Byous.
• The parameter Q is the number of members of JOI Group.
• The parameters A, B, L, C are arrays of length M. They mean the road i (0 ≤ i ≤ M − 1) connects the city A[i] and the city B[i], it takes L[i] Byous to pass through the road i, and a strict security inspection on the road i starts at time C[i].
• The parameters U, V, T are arrays of length Q. They mean the member j (0 ≤ j ≤ Q − 1) departs from the city U[j] at time T[j] and starts traveling to the city V[j].
• This function should return an array answer of long long type and of length Q. It means, for each 0 ≤ j ≤ Q − 1, the minimum amount of time required for the member j to travel from the city U[j] to the city V[j] is answer[j] Byous.

## 입력

The grader reads the following data from the standard input. Given values are all integers.

N M S Q
A0 B0 L0 C0
.
.
.
AM−1 BM−1 LM−1 CM−1
U0 V0 T0
.
.
.
UQ−1 VQ−1 TQ−1

## 출력

The grader outputs Q lines to the standard output. The (k + 1)-th line (0 ≤ k ≤ Q − 1) of output contains answer[k].

## 제한

• 2 ≤ N ≤ 90.
• N − 1 ≤ M ≤ N(N − 1)/2.
• 2 ≤ S ≤ 1 000 000 000 000 000 = 1015.
• 1 ≤ Q ≤ 3 000 000.
• 0 ≤ Ai ≤ N − 1 (0 ≤ i ≤ M − 1).
• 0 ≤ Bi ≤ N − 1 (0 ≤ i ≤ M − 1).
• Ai ≠ Bi (0 ≤ i ≤ M − 1).
• (Ai, Bi) ≠ (Ak, Bk), (Ai, Bi) ≠ (Bk, Ak) (0 ≤ i < k ≤ M − 1).
• 1 ≤ Li < S (0 ≤ i ≤ M − 1).
• Li ≤ Ci < S (0 ≤ i ≤ M − 1).
• You can travel from any city to any other city by passing through some of the roads.
• 0 ≤ Uj ≤ N − 1 (0 ≤ j ≤ Q − 1).
• 0 ≤ Vj ≤ N − 1 (0 ≤ j ≤ Q − 1).
• Uj ≠ Vj (0 ≤ j ≤ Q − 1).
• 0 ≤ Tj < S (0 ≤ j ≤ Q − 1).

## 서브태스크

번호 배점 제한
1 5

N ≤ 40, Q ≤ 1 000.

2 20

N ≤ 40, Uj = 0 (0 ≤ j ≤ Q − 1).

3 10

N ≤ 40.

4 35

N ≤ 60.

5 30

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

## 예제 출력 1

3
8
14
2
5
7

This sample input satisfies the constraints of Subtasks 1, 3, 4, 5.

At time 5, the member 0 starts traveling from the city 0 to the city 3. If the member 0 travels in the following way, it takes 3 Byous.

• Using the road 1, the member 0 departs from the city 0 at time 5, and arrives at the city 2 at time 7.
• Using the road 4, the member 0 departs from the city 2 at time 7, and arrives at the city 3 at time 8.

Since this is the minimum value, we have answer[0] = 3.

At time 7, the member 1 starts traveling from the city 0 to the city 3. If the member 1 travels in the following way, it takes 8 Byous.

• Using the road 0, the member 1 departs from the city 0 at time 7, and arrives at the city 1 at time 10.
• Using the road 2, the member 1 departs from the city 1 at time 10, and arrives at the city 2 at time 14.
• Using the road 4, the member 1 departs from the city 2 at time 14, and arrives at the city 3 at time 15.

Since this is the minimum value, we have answer[1] = 8.

At time 9, the member 2 starts traveling from the city 0 to the city 3. If the member 2 travels in the following way, the member 2 arrives at the city 3 at time 3 on the next day. In total, it takes 14 Byous.

• The member 2 stays in the city 0 until time 0 on the next day.
• Using the road 1, the member 2 departs from the city 0 at time 0, and arrives at the city 2 at time 2.
• Using the road 4, the member 2 departs from the city 2 at time 2, and arrives at the city 3 at time 3.

Since this is the minimum value, we have answer[2] = 14.

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

## 예제 출력 2

42
32
4
93
99
6
102
60
39

This sample input satisfies the constraints of all Subtasks.

## 예제 입력 3

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

## 예제 출력 3

72937946261976
929038398222642
702857945988825
272921388674172
580895059624855
181808439529442
117602869946965
569788353034530
1181546234307589
244230056736534
513790925121797
617759130113052
674500988551485

This sample input satisfies the constraints of Subtasks 1, 3, 4, 5.

## 제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

## 채점 및 기타 정보

• 예제는 채점하지 않는다.