Buses

Input

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

Output

Print the minimum time when Maria can reach village $v$. If it is not possible to get from $d$ to $v$ using the given bus trips, output $-1$.

Examples