Човен#5245
Човен вікінгів пливе по неосяжному океану у пошуках Вальгалли. Кермо давно втрачено, половина весел — тим більше, так що усі повороти він може здійснити лише за допомогою водяних вирів, яких на карті штук. Але і це не так просто, тому і до, і після повороту човен може направлятись лише на північ, південь, захід або схід. На першому вирі починає він свій шлях, і на останньому завершиться його шлях. Але ось скільки сил залишиться для останньої битви? Зіграйте проти підступного Локі, запропонуйте кращий шлях для човна. Боги вважатимуть шлях кращим, якщо він вимагатиме сил на мінімальну кількість поворотів, а серед таких ще й виявиться найкоротшим. Пам'ятайте, що на початку шляху човен напрямлено на північ.
Перший рядок вхідного файлу містить єдине ціле число .
Наступні рядків містять по два цілих числа кожен — координати відповідного виру.
Усі вири знаходяться у різних точках. 2 \leq n \leq 100000, усі координати за модулем не перевищують 10^9. Північ розміщено у напрямку збільшення координати .
Виведіть у вихідний файл два рядки. Перший з них повинен містити два цілих числа: шукану мінімальну кількість поворотів та шукану мінімальну відстань.
У другому ж повинен міститися опис оптимального шляху: номери вирів у порядку їх проходження без повторів, починаючи з першого та завершуючи останнім.
Якщо човну доведеться блукати по морю, не знаходячи шляху, виведіть у єдиному рядку два числа .
Приклад 1