There are buses between some villages in the Vasyuki region. Since the passenger traffic here is not very large, the buses run only a few times a day.
Maria Ivanovna needs to get from village d to village v as quickly as possible (she is considered to be in village d at time 0).
Input
First enter the number N – total number of villages (1 <= N <= 100), then the village numbers d and v, followed by the number of bus trips R (0 <= R <= 10000). The following are descriptions of bus routes. Each flight is given by the departure village number, departure time, destination village and arrival time (all times – are integers from 0 to 10000). If at time t a passenger arrives at some village, then he can leave it at any time starting from t.
Output
Print the minimum time when Maria Ivanovna can be in the village v. If she can't get from d to v using the given bus routes, print -1.
Examples
| # |
Input |
Output |
| 1 |
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
|
5 |