In a directed graph, an edge is given by 4 numbers: the start and end vertices, the departure time, and the arrival time. Moreover, the arrival time may be less than or equal to the departure time.
Passenger flights are made between N settlements by time machines.
At time 0 you are at point A. You are given a flight schedule. It is required to be at point B as early as possible (that is, at the smallest possible moment in time).
At the same time, it is allowed to make transfers from one flight to another. If you arrive at some point at time T, then you can leave it on any flight that departs from this point at time T or later (but not earlier).
Input
The first line contains the number N – the number of settlements (1<=N<=1000). The second line contains two numbers A and B – start and end point numbers. The third line specifies K – number of flights ( 0K1000). The next K lines contain flight descriptions, one per line. Each description is a quadruple of integers. The first number of each four sets the number of the departure point, the second – departure time, third – destination, fourth – Arrival time. Item numbers – natural numbers from 1 to N. Destination and origin can be the same. Time is measured in some absolute units and is given as an integer, modulo not exceeding 109. Since flights are made by time machines, the arrival time can be either greater than the departure time, or less than or equal to it.
It is guaranteed that the input data is such that it is always possible to get from point A to point B.
Output
Print the minimum time when you can be at point B.
|
Enter |
Output |
|
2
1 1
2
|
0 |
|
1
1 1
3
1 3 1 -5
1-5 1-3
1-4 1-10
|
-10 |
|
5
1 2
6
1 0 3 10
4 2 2 -10
4 14 2 -7
3 10 2 10
2 0 4 2
3 10 4 12
|
-10 |