6. Interpol

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.