Interpol naháňa nebezpečného zločinca: doktora Horibilného. Pomocou interpolácie (ako ináč) práve zistili jeho približnú polohu – niekedy dnes sa zjaví niekde na dlhej rovnej ceste vedúcej cez soľné polia v Utahu. Rýchlo tam preto presmerovali kamery všetkých špionážnych satelitov.

Každý z týchto satelitov má slepé miesto. Toto má konštantnú veľkosť a ako sa satelit hýbe, aj toto miesto sa hýbe po ceste – budeme predpokladať, že rovnomernou konštantnou rýchlosťou.

Je možné, že napriek množstvu satelitov nedokáže Interpol zločinca nájsť?

Úloha

Na osi $x$ (predstavujúcej cestu) sa nachádza $n$ uzavretých intervalov. Každý interval predstavuje slepé miesto jedného zo satelitov. V tejto chvíli platí, že $i$-ty z týchto intervalov pokrýva súradnice $[\ell_i,r_i]$. Interval $i$ sa hýbe doprava rýchlosťou $v_i$. Teda po uplynutí času $t$ bude slepý interval satelitu $i$ začínať na súradnici $\ell_i + t\cdot v_i$.

Zistite, či niekedy bude existovať nejaká časť cesty, ktorú v danom okamihu nebude nahrávať žiadny satelit. Ak áno, vypočítajte, aký najdlhší úsek cesty bude mať túto vlastnosť.

Formát vstupu

V prvom riadku vstupu je číslo $n$ ($1\leq n\leq 100\,000$): počet satelitov. V každom z ďalších $n$ riadkov je jedna trojica celých čísel $\ell_i$, $r_i$, $v_i$ ($0\leq \ell_i < r_i \leq 10^6$, $1\leq v_i\leq 10^6$).

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo – najdlhšiu dĺžku intervalu, ktorý v nejakom okamihu nebol v zábere žiadneho zo satelitov.

(Toto číslo môže byť reálne, viď posledný príklad. Vypíšte ho s presnosťou na aspoň 7 desatinných miest. Výstupy, ktoré budú mať od nášho dostatočne malú odchýlku, budú akceptované.)

Ak hľadaný interval (ani degenerovaný) neexistuje, vypíšte namiesto toho číslo $-1$.

Hodnotenie

Vaše riešenia budeme testovať na štyroch sadách vstupov. V jednotlivých sadách platí $n\leq 5$, $n\leq 20$, $n\leq 1\,000$ a $n\leq 100\,000$. V druhej a tretej sade navyše platí, že žiaden vstup nemá výstup $-1$ ani $0$.

Príklady

Input:

2
5 7 1
10 13 1

Output:

-1

Slepé miesta satelitov sa v tejto chvíli neprekrývajú, takže každý bod cesty vidí aspoň jeden z nich. No a keďže sa obe slepé miesta hýbu tou istou rýchlosťou, toto ostane pravdou aj naďalej.

Input:

2
3 7 1
7 18 10

Output:

0

V tomto okamihu ani jeden zo satelitov nezaberá bod na súradnici 7, máme teda interval dĺžky 0, ktorý je nepozorovaný. V budúcnosti už nič lepšie (pre doktora Horibilného) nenastane.

Input:

3
40 140 30
130 180 10
47 190 1

Output:

44.4827586207

V čase $t\approx 1.724$ budú slepé intervaly našich troch satelitov približne $[91.724,191.724]$, $[147.241,197.241]$ a $[48.724,191.724]$, čiže v danom okamihu interval $[147.241,191.724]$ nebude zaberaný ani jedným zo satelitov.