Lai uzvarētu slēpošanas slaloma sacensībās, sportistam slaloma trase jāveic pa visīsāko maršrutu. Naktī pirms sacensībām sportists ir ķēries pie trases kartes izpētes.

Trases sākuma un beigu punkti ir apzīmēti ar diviem punkti plaknē, savukārt vārti, kuriem sportistam jāizbrauc cauri, ir apzīmēti ar taisnes nogriežņiem, kas paralēli koordinātu x asij. Skaitļu virkne, ko veido trases sākuma punkta y koordināta, visu vārtu to izbraukšanas secībā koordinātas un beigu punkta y koordinata, ir stingri dilstoša skaitļu virkne.

Jebkura sportista maršruts sākas trases sākuma punktā, beidzas trases beigu punktā un sastāv no taisnes nogriežņu virknes. Diviem pēc kārtas sekojošiem nogriežņiem viens galapunkts ir kopīgs un atrodas uz nogriežņa, kas apzīmē vārtus. Katrs maršrutā ietilpstošais nogrieznis savieno divus, pēc kārtas sekojošus, vārtus. Trases sākuma punkts ir maršruta pirmā nogriežņa galapunkts, bet trases beigu punkts ir maršruta pēdējā nogriežņa galapunkts.

Uzrakstiet programmu, kas aprēķina īsākā maršruta garumu un nosaka, kura no dotajām atbildēm ir vistuvāk precīzajam atrisinājumam! "Vistuvāk" nozīmē, ka, ja visām dotajām vērtībām tiek aprēķināta starpība (pēc moduļa) starp šo doto un jūsu atrasto atbildi, tad izvēlētajai atbildei šī starpība ir vismazākā.

Ievaddatu pirmajā rindā dota naturāla skaitļa N (vārtu skaits,1 ≤N≤5000) vērtība.

Faila otrajā rindā dotas trases sākuma punkta koordinātas XS un YS, kas atdalītas ar tukšumsimbolu.

Katrā no nākošajām N faila rindām dots pa vienu vārtu aprakstam - trīs veselu skaitļu X1,X2 un Y vērtības, kas atdalītas ar tukšumsimboliem. Zināms, ka X1<X2 un ka šis pieraksts nozīmē, ka šiem vārtiem atbilst nogrieznis ar galapunktiem punktos (X1,Y) un (X2,Y). Vārti ir doti tādā secībā, kā sportistam tie jāizbrauc.

Faila nākošajā rindā dotas trases beigu punkta koordinātas XC un YC, kas atdalītas ar tukšumsimbolu.

Neviena punkta neviena koordināta pēc absolūtās vērtības nepārsniedz 15000.

Tālāk failā seko 100 rindas, kur katrā no tām dots pa vienam atšķirīgam reālam skaitlim - iespējamam dotā uzdevuma atrisinājumam.

Izvaddatu vienīgajā rindā jāizvada naturāls skaitlis - tās atbildes numurs pēc kārtas, kura ir vistuvāk precīzajam īsākā maršruta garumam.

Uzdevums izmantots Horvātijas informātikas olimpiādē 2003.gadā

P.S. Sakarā ar to, ka uzdevumam ievaddati ir ļoti lieli, tie netiks attēloti parauga testu sarakstā. Bet zemāk ir fragments no viena no testiem.

5
0 25
-3 -2 20
-7 -4 15
-6 -4 10
-4 -2 6
-3 -1 2
0 -3
29.3550
29.3553
29.3556
29.3559
29.3562
29.3565
29.3568
...