Buses

Between some villages of Vasyuki district there are buses routes. As the passenger traffic is not very large, the buses run only a few times a day.

Maria Ivanovna wants to get from the village $d$ to the village $v$ as soon as possible (it is assumed that at time $0$ she is in the village $d$).

Input

First given the total number of villages $n$ $(1\le n\le 100)$, $d$ and $v$, then the number of bus lines $r$ $(0\le r\le 10000)$. Then given the description of bus trips. Each route is given by the number of the starting village, time of departure, the destination village and the arrival time (all times are integers from $0$ to $10000$). If at time $t$ the passenger arrives in the village, he can leave it at any time, starting from $t$.

Output

Print the minimum time when Maria Ivanovna can reach the village $v$. If she fails with these bus trips to get from $d$ to $v$, output $-1$.

Examples