Відомо, що ІІ тур Всеукраїнської олімпіади з інформатики відбудеться 16 листопада 2024 року.

Вам задається місяць та день 2024 року. Визначте положення цього дня у році по відношенню до дати другого етапу олімпіади.

Input

Перший рядок містить ціле число ~M~ (~1 \le M \le 12~) - порядковий номер місяця.

У другому рядку записано ціле число ~D~ (~1 \le D \le 31~) - число у вказаному місяці.

Гарантується, що дата коректна.

Output

Вивести:

• 'Before', якщо введена дата наступить до олімпіади;
• 'After', якщо введена дата наступить після олімпіади;
• 'Today', якщо введена дата є 16 листопада.

Sample Input 1

11
15

Sample Output 1

Before

Дмитрик записує статистику баскетбольного матчу. Очки нараховуються так: кидком із-за дуги 3 очки, кидком з гри 2 очки або штрафним кидком 1 очко.

Тепер Дмитрик знає кількість влучних кидків кожного з цих типів очок для двох команд: «Apples» та «Bananas».

Ваше завдання — допомогти Дмитрику визначити, яка команда перемогла.

Input

Перші три рядки описують кидки «Apples», а наступні три рядки описують кидки «Bananas».

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

Кожне число буде цілим числом від 0 до 100 включно.

Output

Вивести один символ:

• ~A~, якщо виграють «Apples»;
• ~B~, якщо виграють «Bananas»;
• ~T~, якщо буде нічия.

Sample Input 1

10
3
7
8
9
6

Sample Output 1

B

Sample Input 2

7
3
0
6
4
1

Sample Output 2

T

Ми часто додаємо смайлики до наших текстових повідомлень, щоб вказати, що ми відчуваємо. Три послідовні символи ':-)' вказують на радість, а три послідовні символи ':-(' - на смуток.

Напишіть програму, щоб визначити загальний настрій повідомлення.

Обмеження

• ~S~ містить символи проміжків 'a'..'z', 'A'..'Z' та знаки пунктуації.
• ~1 \le |S| \le 255~

Input

Єдиний рядок містить текстове повідомлення ~S~.

Output

Вивести:

• 'none', якщо рядок вводу не містить жодного веселого або сумного смайлика
• 'unsure', якщо вхідний рядок містить однакову кількість веселих і сумних смайликів,
• 'happy', якщо у рядку ~S~ більше смайликів ':-)'
• 'sad', якщо у рядку ~S~ більше смайликів ':-('.

Sample Input 1

How are you :-) doing :-( today :-)?

Sample Output 1

happy

Sample Input 2

:)

Sample Output 2

none

Шеф попросив вас додати послідовність цілих додатних чисел, щоб визначити прибуток компанії за певний період. На жаль, він має ваду і час від часу неправильно читає числа. Добре те, що шеф розуміє, коли неправильно сказав число, і каже «нуль», що означає «ігнорувати поточне останнє число».

Щеф може повторювати помилки, але завжди промовить «нуль» для кожної зробленої помилки (можливо, із запізненням).

Наприклад, він може сказати: «Один, три, п'ять, чотири, нуль, нуль, сім, нуль, нуль, шість» - при цьому загальна сума дорівнює 7. Перші два '0' ігнорують 4 і 5, а другі два - 7 та 3. Отже, залишиться 1 і 6.

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

Напишіть програму, яка зчитує послідовність вказівок шефа та обчислює правильну суму.

Input

Перший рядок містить ціле число ~n~ (~1 \le n \le 10^5~) - кількість названих чисел, включаючи нулі.

Наступні ~n~ містять по одному числу в межах від 1 до 100 або 0.

Output

Вивести одне число - знайдену суму. Гарантується, що результат буде не більший ~10^6~.

Sample Input 1

4
3
0
4
0

Sample Output 1

0

Sample Input 2

3
10
0
1

Sample Output 2

1

Sample Input 3

10
1
3
5
4
0
0
7
0
0
6

Sample Output 3

7

З незапам'ятних часів громадяни Паскальстану та Сігланди ворогували. Тепер вони нарешті підписали перемир'я і вирішили взяти участь у велопробігу на честь перемир'я.

Є ~N~ громадян з кожної країни. Вони повинні бути розподілені по парах так, щоб кожна пара містила одну особу з Паскальстану та одну особу з Сігланди.

Кожен громадянин має свою швидкість руху на велосипеді. У парі найшвидша людина завжди керуватиме велосипедом-тандемом, а повільніша просто насолоджується поїздкою. Іншими словами, якщо члени пари мають швидкості ~a~ і ~b~, то швидкість велосипеда пари дорівнює ~max(a,b)~. Загальна швидкість є сумою індивідуальних швидкостей велосипедів.

Напишіть програму, що дасть відповіді на такі запити двох типів:

• 1: яка мінімальна загальна швидкість з усіх можливих розподілів на пари?
• 2: яка максимальна загальна швидкість з усіх можливих розподілів на пари?

Input

Перший рядок містить тип запитання, яке ви маєте розв'язати: 1 або 2.

Другий рядок містить ціле число ~N~ (~1 \le N \le 100~).

У третьому рядку через пропуски записані ~N~ цілих чисел - швидкості жителів Паскальстану.

У четвертому рядку через пропуски записані ~N~ цілих чисел - швидкості жителів Сігланди.

Швидкість кожної людини буде цілим числом від 1 до ~10^6~.

Output

Виведіть максимальну або мінімальну загальну швидкість, яка відповідає запиту 1 або 2.

Sample Input 1

1
3
5 1 4
6 2 4

Sample Output 1

12

Sample Input 2

2
3
5 1 4
6 2 4

Sample Output 2

15

Notes

До прикладу 1

Існує єдине оптимальне рішення:

• оберіть людей зі швидкостями 5 і 6
• оберіть людей зі швидкостями 1 і 2
• оберіть людей зі швидкостями 4 і 4

Можливо, ви знаєте, що 14 березня відоме як день числа Пі - 3.14 (це третій місяць і чотирнадцятий день).

Математики святкують цей день поїданням святкового торта.

Припустимо, що у вас є ~n~ кусочків торта і ~k~ людей, які стоять у черзі за тортом. Всі кусочки торта будуть обов'язково роздані. Кожна людина отримає принаймні один кусочок торта. Математики вирішили трохи змудрувати і поділ буде виконуватися таким чином, що кожна людина отримає принаймні стільки кусочків торта, скільки людина перед нею.

Наприклад, якщо є 8 кусочків торта і 4 людини в черзі, то можна роздати торт наступними п'ятьма способами (перша людина в черзі буде першим номером у списку):(1,1,1,5), (1,1,2,4), (1,1,3,3), (1,2,2,3),(2,2,2,2).

Зауважте, що якщо ~k=n~, то існує лише один спосіб роздати торт: кожна особа отримує рівно один кусочок. Крім того, якщо ~k=1~, то також є лише один спосіб роздати торта: одна людина отримує всі кусочки.

Напишіть програму, яка визначає кількість способів, якими можна роздавати всі кусочки торта.

Обмеження

• ~1 \le n \le 250~
• ~1 \le k \le n~

Input

Перший рядок містить ціле число ~n~ - кількість кусочків торта.

У другому рядку записано ціле число ~k~ - кількість людей.

Output

Вивести одне ціле число - кількість способів розподілу торта згідно описаного правила.

Результат гарантовано буде меншим ніж ~2^{31}~ .

Sample Input 1

8
4

Sample Output 1

5

Sample Input 2

6
2

Sample Output 2

3

Дмитрик захопився вивченням графів і сьогодні він намагається розв'язати задачу, яка його особливо захопила.

Отже, є простий орієнтований граф з ~N~ вершинами та ~M~ ребрами. Вершини пронумеровані від 1 до ~N~. ~I~-те ребро (~1 \le i \le M~) спрямоване від вершини ~a_i~ до вершини ~b_i~.

Дмитрик хоче визначити, чи існує такий цикл, що містить вершину 1, і якщо такі цикли існують, то треба знайти мінімальну кількість ребер серед таких циклів.

Обмеження

• ~2 \le N \le 2 \times 10^5~
• ~1 \le M \le min(\frac{N(N-1)}{2},2 \times 10^5)~
• ~1 \le a_i \le N~
• ~1 \le b_i \le N~
• ~a_i \neq b_i~
• ~(a_i, b_i) \neq (a_j, b_j)~ і ~(a_i,b_i) \neq (b_j,a_j)~, якщо ~i \neq j~
• Усі вхідні значення є цілими числами.

Input

Перший рядок вхідного потоку містить цілі числа ~N, M~.

Наступні ~M~ рядків містять цілі числа ~a_i, b_i~. Числа розділяються пропуском.

Output

Якщо існують цикли, які містять вершину 1, то виведіть мінімальну кількість ребер серед таких циклів або -1 у випадку, коли такого циклу немає.

Sample Input 1

3 3
1 2
2 3
3 1

Sample Output 1

3

Sample Input 2

3 2
1 2
2 3

Sample Output 2

-1

Sample Input 3

6 9
6 1
1 5
2 6
2 1
3 6
4 2
6 4
3 5
5 4

Sample Output 3

4