Vasyuki rayonunun bəzi kəndləri arasında avtobus marşrutları fəaliyyət göstərir. Sərnişin axını çox böyük olmadığından avtobuslar gündə bir neçə dəfə işləyir.

Mariya İvanovna kənddən $d$ kəndə $v$ tez çatmaq istəyir (ehtimal olunur ki, $0$ saatında o, $d$ kənddədir).

\InputFile

Əvvəlcə kəndlərin ümumi sayı $n$$(1 ≤ n ≤ 100)$, $d$ və $v$, sonra avtobus xətlərinin sayı verilmişdir. $r$$(0 ≤ r ≤ 10000)$. Daha sonra avtobus səfərlərinin təsviri verildi. Hər bir marşrut başlanğıc kəndin nömrəsi, gediş vaxtı, təyinat kəndi və gəliş vaxtı ilə verilir (bütün vaxtlar $0$-dan $10000$-a qədər olan tam ədədlərdir). Sərnişin $t$ vaxtında kəndə çatarsa, $t$-dan başlayaraq istənilən vaxt onu tərk edə bilər.

\OutputFile

Mariya İvanovnanın kəndə $v$ çata biləcəyi minimum vaxtı çap edin. Əgər o, $d$-dan $v$-a getmək üçün bu avtobus səfərlərində uğursuz olarsa, $-1$ çıxın.