1. Ламана

Максимальна оцінка: 100 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 256 MБ
Вхідний файл: polyline.in
Вихідний файл: polyline.out
Програма: polyline.*

Завдання
На площині позначено кілька точок. Якщо це можливо, побудуйте замк­не­ну ламану без самоперетинів, що проходить через усі ці точки і не має відмін­них від них вершин.

Вхідні дані
У першому рядку вхідного файлу задано кількість точок n, 3 ≤ n < 2017. У n наступних рядках вказано по дві координати кожної точки: абсцису та ординату відповідно. Повторення точок немає. Всі координати — цілі числа, що за модулем не перевищують 10 000.

Вихідні дані
Якщо побудувати потрібну замкнену ламану неможливо, вивести 0. інакше вивести порядок, у якому задані точки розташовано на ламаній, тобто порядок обходу всіх цих точок, починаючи з довільного місця і в довіль­ному напрямку. Нумерація точок почи­нається з одиниці. Ламаних, що задовольняють умову, може бути кілька. Достат­ньо знайти хоча б одну.

Приклад

2. Печери

Максимальна оцінка: 100 балів
Обмеження на час: 5 сек.
Обмеження на пам’ять: 128 MБ
Вхідний файл: caves.in
Вихідний файл: caves.out
Програма: caves.*

Пер Ґюнт, герой п’єси норвезького письменника Генріка Ібсена, потрапив у полон короля тролів. Щоб визволитися, Пер Ґюнт повинен перемогти у грі, яку король пропонує своїм бранцям. Правила гри такі:

• є 10 печер , деякі з яких сполучені між собою;

• бранець грає протягом m днів:

  • у перший день він може вибрати собі довільну печеру;

  • кожного наступного дня він може або залишитися у печері, у якій перебуває, або перейти у будь-яку іншу печеру, до якої є хід з поточної печери;

• кожного дня король винагороджує бранця певною наперед обумовленою кількістю золотих монет, яка залежить і від печери, і від номера дня;

• якщо за всю гру бранець накопичить кількість монет, виражену одним з l «коро­лів­ських чисел», то бранця навіки залишають у полоні — він програв. Інакше його відпускають на волю з виграшем — усією накопиченою за час гри кількістю монет.

Завдання
Визначити N_w, p_max, p_min — відповідно кількість різних виграшів, найбільший і найменший виграші.

Вхідні дані
Перший рядок файлу містить десяткові записи натуральних чисел m, l, де m ≤ 60. Кожний з наступних 10 рядків містить по 10 цілих чисел — нулів або одиниць. При 1 ≤ j, k ≤ 10: якщо k-те число (j + 1)-го­ рядка файлу дорівнює 1, то з j-ої­ печери можна потрапити безпосередньо до k-ої печери і навпаки. Інакше це зробити неможливо. Кожний з наступних m рядків містить по 10 невід’ємних цілих чисел. При 1 ≤ j ≤ m і 1 ≤ k ≤ 10: k-те число (j + 11)-го рядка — кількість монет, які отримує гравець як винагороду за перебування у j­-ий день у k-ої печері. Останній (m + 12)-ий­ рядок містить у поряд­ку спадання l різних цілих невід’ємних «королів­ських чисел», кожне з яких менше від 2⁶⁴. Останнє число у цьому рядку — нуль.

Вихідні дані
Єдиний рядок файлу має містити десяткові записи трьох чисел: N_w, p_max, p_min. Якщо N_w = 0, то p_max = p_min = 0. Відомо, що p_max < 2⁶⁴, l + N_w ≤ 106.

Приклад