Максимальна оцінка за кожну з чотирьох задач — 100 балів.
Для всіх задач:
обмеження на час — 1 секунда / тест;
обмеження на пам’ять — 256 МБ.

1. Митько та подібні трикутники
Назва програми: similar.*

Якось на уроці геометрії Митько дізнався, що два трикутники є подібними тоді й лише тоді, коли три сторони одного з них є пропорційними трьом сторонам іншого. Допоможіть Митькові з домашнім завданням: визначити, чи є два заданих трикутники подібними.

Вхідні дані
У вхідному файлі вказано шість натуральних чисел: перші три — довжини сторін першого трикутника, наступні три — довжини сторін другого трикутника. Усі числа менші за тисячу. Відомо, що з відрізків заданих довжин дійсно можна скласти трикутники.

Вихідні дані
У вихідний файл виведіть число 1, якщо задані трикутники подібні; в іншому разі виведіть 0.

Приклади

Пояснення до прикладів
У першому прикладі трикутники подібні, бо їхні сторони пропорційні: 2 ∶ 4 = 3 ∶ 6 = 4 ∶ 8. У другому прикладі сторони також пропорційні, хоч і не в такому порядку, в якому задані у вхідному файлі: 3 ∶ 30 = 5 ∶ 50 = 3 ∶ 30. У третьому прикладі трикутники не подібні, адже, незалежно від порядку, їхні сторони не є пропорційними.

2. Митько та дивовижний острів
Назва програми: island.cpp / island.pas

Якось на уроці географії Митько почув про незвичайний острів, що має форму круга: посередині острова височіє скеля, а населення живе у хижах уздовж периметра острова і через прямовисність скелі може пересуватися від хижі до хижі також виключно по периметрі. Для зручності вважатимемо, що периметр острова розбито на кілька однакових частин, які умовно назвемо секторами, і з однієї такої частини в сусідню можна перейти рівно за хвилину. У деяких секторах розташовано по хижі (але не більш ніж одна хижа в секторі). Визначте, за який час можна подолати відстань між парою найвіддаленіших хиж на острові.

Вхідні дані
У першому рядку вхідного файлу вказано два натуральних числа n та h — кількість секторів та хиж на острові відповідно. Відомо, що 2 ⩽ h ⩽ n ⩽ 500 000. Сектори занумеровано числами від 1 до n у тому порядку, в якому вони йдуть на острові (при цьому сектори з номерами 1 та n замикають коло і також є сусідніми). У другому рядку в порядку зростання вказано номери секторів, у яких є хижі.

Вихідні дані
У вихідний файл виведіть єдине число — відстань між двома найвіддаленішими хижами острова, тобто час у хвилинах, за який можна дійти від однієї з цих хиж до іншої.

Приклади

Пояснення до прикладів
У першому прикладі найвіддаленішими є перша та остання хижі, тож відповідь дорівнює 20 − 3 = 17. У другому прикладі перша та остання хижі вже не є найвіддаленішими, адже між ними можна пройти за 5 хвилин (таким чином: сектор 3 — сектор 2 — сектор 1 — сектор 22 — сектор 21 — сектор 20). Найвіддаленішими натомість є хижі в секторах 7 і 19: вибравши оптимальний напрямок руху, дійти від однієї з них до іншої можна лише за 10 хвилин.

3. Митько та арифметичні прогресії
Назва програми: progress.*

Якось на уроці алгебри Митько довідався, що арифметичною прогресією називають послідовність чисел, у якій різниця між кожними двома сусідніми членами однакова. Щоб учні краще засвоїли матеріал, учитель взяв деякі дві арифметичні прогресії, кожна з яких складається з n натуральних чисел, перемішав між собою всі 2n чисел (вони виявилися попарно різними) і виписав утворену послідовність на дошці. Допоможіть Митьку виконати вчителеве завдання: відновити з заданого набору чисел дві початкові арифметичні прогресії. Вхідні дані гарантують, що зробити це є рівно один спосіб.

Вхідні дані
У першому рядку вхідного файлу вказано натуральне число n — кількість членів кожної з двох арифметичних прогресій, 3 ⩽ n ⩽ 100 000. У другому рядку записано 2n різних натуральних чисел, менших за 10⁹, — перемішані елементи обох прогресій.

Вихідні дані
У перший рядок вихідного файлу виведіть усі члени першої арифметичної прогресії у порядку зростання, а в другий рядок — усі члени другої арифметичної прогресії у порядку зростання. Прогресії виведіть у такому порядку, щоб перше число в першому рядку було меншим за перше число у другому рядку.

Приклад

Пояснення до прикладу
Виведені у вихідний файл послідовності є арифметичними прогресіями:
9 − 2 = 16 − 9 = 23 − 16;
7 − 3 = 11 − 7 = 15 − 11.

4. Митько та міжпланетна подорож
Назва програми: journey.*

Якось після важкого дня у школі з уроками астрономії, фізики та економіки у голові Митька все перемішалося, і хлопцю наснився дивний сон. У віддаленому майбутньому люди заселяють n планет, між якими пересуваються за допомогою телепортації. Для зручності планети занумеровано числами від 1 до n. Процес телепортації обслуговують m різних компаній, і вони конкурують між собою. Тому телепортуватися можнане між будь-якою парою планет, а лише між тими, які обслуговує одна й та сама компанія. На щастя, одну й ту саму планету може обслуговувати відразу кілька різних компаній. До того ж відомо, що з кожної планети можна переміститися на будь-яку іншу якщо й не за одну, то принаймні за декілька послідовних телепортацій. З’ясуйте, за яку найменшу кількість послідовних телепортацій можна переміститися з планети 1 на планету n.

Вхідні дані
У першому рядку вхідного файлу записано два натуральних числа n та m — кількість планет та компаній відповідно; n ⩾ 3, m ⩾ 2, а добуток цих двох чисел не перевищує мільйона. Кожен з наступних n рядків містить по m цифр, не розділених пробілом, та задає інформацію про відповідну планету (у першому з цих рядків — інформація про планету 1, в останньому — про планету n): якщо цифра на позиції k в рядку є одиницею, то компанія під номером k обслуговує дану планету; якщо ж ця цифра нуль, то не обслуговує. Кожна компанія обслуговує хоча б дві планети.

Вихідні дані
У вихідний файл виведіть єдине число — найменшу кількість послідовних телепортацій, необхідних, щоб з планети 1 дістатися на планету n.

Приклад

Пояснення до прикладу
Першу планету обслуговує тільки друга компанія, тому з неї можна потрапити на другу і третю планети, але не на четверту. Зате за дві телепортації — з транзитом через третю планету — з першої на четверту потрапити вже можна.