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

1. Стрілки
Назва програми: hands.pas / hands.cpp

В Орисі та Марисі є по одному улюбленому числу в межах від 1 до 12 включно, причому ці числа не обов’язково різні. З’ясуйте, скільки протягом доби є таких моментів часу, що хоча б одна зі стрілок годинника (годинна або хвилинна) точно вказує на улю-блене число принаймні однієї з дівчат.

Вхідні дані
У вхідному файлі вказано два натуральних числа: улюблене число Орисі та улюблене число Марисі.

Вихідні дані
У вихідний файл вивеcти кількість відповідних моментів часу протягом однієї доби.

Приклад

2. Сірники
Назва програми: matches.pas / matches.cpp

Орися та Марися люблять гратися з сірниками. Кожна з дівчат має по n сірників. Орися хоче викласти із своїх сірників якомога більше число, а Марися — якомога менше число, причому дівчата хочуть використати всі свої сірники. Допоможіть Орисі та Марисі. Те, як з сірників викладаються цифри, ви можете подивитися на рисунку нижче.

Дівчата знають, що ставити на початок чисел нулі не можна.

Вхідні дані
У вхідному файлі записано натуральне число n. Воно є не меншим за 2 і не перевищує 2000.

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

Приклад

3. Цукерки
Назва програми: candy.pas / candy.cpp

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

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

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

Приклади

Пояснення до прикладів
При початковому розташуванні цукерок 3, 6, 9, 3 перший гном отримає від другого 6/(4 − 1) = 2 цукерки, від третього — 9/(4 − 1) = 3 цукерки, а від четвертого — 3/(4 − 1) = 1 цукерку (разом він матиме 2 + 3 + 1 = 6 цукерок, бо свої три він віддасть); другий гном отримає 3/3 + 9/3 + 3/3 = 5 цукерок; третій матиме 3/3 + 6/3 +3/3 = 4 цукерки; четвертий —  3/3 + 6/3 + 9/3 = 6 цукерок. Можна переконатися, що в другому прикладі жодного можливого початкового розташування не існує.

4. Поїзди
Назва програми: trains.pas / trains.cpp

У місті, де живуть Орися та Марися, є n ліній метрополітену і m станцій (деякі з них можуть бути станціями пересадки і належати відразу кільком лініям). Усі станції занумеровано натуральними числами від 1 до m. Орися живе біля станції з номером 1, а Марися — біля станції з номером m. Знаючи, скільки хвилин забирає проїзд між кожними двома сусідніми станціями на кожній лінії, визначте, за який найменший час Орися зможе доїхати до Марисі. Відомо, що між станціями, де живуть дівчата, існує сполучення (можливо, з пересадками). Пересадка між лініями, а також вхід у метро (на будь-яку лінію) та вихід (з будь-якої лінії) здійснюють миттєво. Поїзди ходять щохвилини, тож Орися не чекатиме поїздів на станціях. Часом зупинки поїзда на станції також можна знехтувати. На всіх лініях поїзди рухаються в обидва боки.

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

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

Приклад

Пояснення до прикладу
Маємо три лінії метро, що проходять через дев’ять станцій. Схему ліній та час переїзду між кожними двома сусідніми станціями показано на наступному рисунку.

Щоб дістатися з першої до дев’ятої станції якнайшвидше, зробимо так: сядемо на другу лінію (з сімома станціями), доїдемо до сьомої станції, пересядемо на першу лінію (з чотирма станціями), доїдемо до восьмої станції та знову пересядемо на другу лінію, вийдемо на дев’ятій станції. Це забере 1 + 2 + 1 = 4 хвилини. Альтернативні маршрути без пересадок тривають 1 + 2 + 3 + 1 = 7  хвилин по другій лінії та 8 хвилин по третій.