Qayıq
Vikinqlərin gəmisi geniş okeanda Valhalla axtarışında üzür. Sükan çoxdan itirilib, avarların yarısı isə işə yaramır, belə ki, bütün dönmələri yalnız xəritədəki n su girdablarının köməyi ilə edə bilərlər. Amma bu da o qədər asan deyil, çünki dönmədən əvvəl və sonra gəmi yalnız şimal, cənub, qərb və ya şərq istiqamətində hərəkət edə bilər. Gəmi ilk girdabdan yoluna başlayır və son girdabda yolunu tamamlayacaq. Amma son döyüş üçün nə qədər güc qalacaq? Hiyləgər Loki ilə oynayın və gəmi üçün ən yaxşı yolu təklif edin. Tanrılar yolu daha yaxşı hesab edəcəklər, əgər o, minimum dönmə sayını tələb edərsə və belə olan halda ən qısa yol olar. Unutmayın ki, yolun əvvəlində gəmi şimala yönəlib.
Giriş verilənləri
Giriş faylının ilk sətiri tək tam ədəd n ehtiva edir. Növbəti n sətir hər biri iki tam ədəd - müvafiq girdabın koordinatlarını ehtiva edir. Bütün girdablar müxtəlif nöqtələrdə yerləşir. 2 ≤ n ≤ 100000, bütün koordinatlar modulu 10^9-dan çox deyil. Şimal y koordinatının artması istiqamətində yerləşir.
Çıxış verilənləri
Çıxış faylında iki sətir yazın. Birincisi iki tam ədəd ehtiva etməlidir: axtarılan minimum dönmə sayı və axtarılan minimum məsafə. İkincisi isə optimal yolun təsvirini ehtiva etməlidir: təkrarlanmadan keçilən girdabların nömrələri, birincidən başlayaraq sonuncu ilə bitən.
Əgər gəmi dənizdə dolaşmalı olsa, yolu tapa bilməsə, tək sətirdə iki -1 ədədini yazın.