В Аліси зараз ~a~ гривень. Вона пам'ятає, що Петрик винен їй ~b~ гривень, а Світлана винна їй ще ~c~ гривень. Проте Аліса винна Ромчику ~d~ гривень.

Якщо всі віддадуть борги, то скільки гривень буде в Аліси?

Формат вхідних даних

Перший рядок містить одне ціле число ~a~ (~1 \leq a \leq 100~) — кількість гривень, які є в Аліси.

Другий рядок містить одне ціле число ~b~ (~1 \leq b \leq 100~) — кількість гривень, які винен Петрик Алісі.

Третій рядок містить одне ціле число ~c~ (~1 \leq c \leq 100~) — кількість гривень, які винна Світлана Алісі.

Четвертий рядок містить одне ціле число ~d~ (~1 \leq d \leq 100~) — кількість гривень, які винна Аліса Ромчику.

Гарантується, що в Аліси в кінці буде невід'ємна кількість гривень.

Формат вихідних даних

Виведіть одне ціле число — відповідь на задачу.

Приклад вхідних даних

5
2
3
4

Приклад вихідних даних

6

Приклад вхідних даних

7
4
4
15

Приклад вихідних даних

0

У Петрика є два числа ~a~ та ~b~ (~a \leq b~). Він знайшов середнє арифметичне цих чисел (нехай, це буде число ~c~), яке виявилось теж цілим. Тобто, ~c = \frac{a+b}{2}~.

Вам дано число ~a~ (тобто менше з тих двох чисел), а також дано число ~c~. Знайдіть ~b~.

Формат вхідних даних

Перший рядок містить одне ціле число ~a~ (~1 \leq a \leq 100~).

Другий рядок містить одне ціле число ~c~ (~a \leq c \leq 100~).

Формат вихідних даних

Виведіть одне ціле число — ~b~.

Приклад вхідних даних

3
7

Приклад вихідних даних

11

Сьогодні Петрик нарешті написав екзамен з математичного аналізу. Всього на екзамені було ~a~ легких задач та ~b~ складних, при цьому кожна складна задача важила вдвічі більше балів ніж проста.

Петрик пам'ятає, що не зміг розв'язати рівно ~x~ легких та рівно ~y~ складних задач, а всі інші задачі він точно розв'язав правильно.

Тепер же Петрик цікавиться, чи радіти йому успішній здачі екзамену, якщо для складання екзамену треба набрати хоча б ~51\%~ від максимальної кількості балів.

Зверніть увагу, що, якщо Петрик отримає ~50.5\%~ балів, то екзамен вважається не зданим.

Формат вхідних даних

Перший рядок містить чотири цілі числа ~a, b, x~ та ~y~ (~1 \le x \le a \le 10^5, 1 \le y \le b \le 10^5~).

Формат вихідних даних

У випадку якщо Петрик склав екзамен виведіть YES, інакше NO

Приклад вхідних даних

10 3 10 3

Приклад вихідних даних

NO

Приклад вхідних даних

12 4 3 2

Приклад вихідних даних

YES

Приклад вхідних даних

5 3 2 2

Приклад вихідних даних

NO

Пояснення

У першому прикладі Петрик не зміг вирішити жодної задачі, а отже не склав екзамен.

У другому прикладі Петрик не розв'язав ~3~ з ~12~ простих задач та ~2~ з ~4~ складних. Це значить, що хлопець успішно розв'язав ~9~ з ~12~ простих задач та ~2~ з ~4~ складні задачі. Якщо кожна проста задача коштує ~c~ балів, то хлопець отримав за прості задачі ~9c~ балів, а за складні ~2 \cdot 2c~ балів, що в сумі дає результат ~13c~ балів. Максимальний можливий результат - це ~12c+2 \cdot 4c=20c~ балів, тоді, порахувавши результат Петрика у відсотках від максимальної оцінки, отримаємо ~65\%~, що більше ~51\%~.

У третьому прикладі Петрик не розв'язав ~2~ з ~5~ простих задач та ~2~ з ~3~ складних. Це значить, що хлопець успішно розв'язав ~3~ з ~5~ простих задач та ~1~ з ~3~ складних задач. Якщо кожна проста задача коштує ~c~ балів, то хлопець отримав за прості задачі ~3c~ балів, а за складні ~2 \cdot 1c~ балів, що в сумі дає результат ~5c~ балів. Максимальний можливий результат - це ~5c+2 \cdot 3c=11c~ балів, тоді, порахувавши результат Петрика у відсотках від максимальної оцінки, отримаємо приблизно ~45\%~, що менше ~51\%~

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

Оскільки він стоїть прямо поруч зупинок публічного транспорту, то знає, що найближчий автобус приїде через ~d_b~ хвилин, дорога на ньому займає ~t_b~ хвилин, а дорога пішки від зупинки приїзду до торгового центру ~w_b~ хвилин.

Петрику також доступне метро, очікування потягу у якому займає ~d_m~ хвилин, поїздка ~t_m~ хвилин, а дорога пішки від станції прибуття до торгового центру ~w_m~ хвилин.

З врахуванням нагальності поїздки хлопець розглядає і варіант таксі, очікування якого згідно з мобільною програмою займе ~d_t~ хвилин, а час поїздки становить ~t_t~ хвилин.

Підкажіть, будь ласка, Петрику, який транспорт йому краще використовувати, щоб потрапити у торговий центр як можна скоріше.

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

Формат вхідних даних

Перший рядок містить три цілі числа ~d_b~, ~t_b~ та ~w_b~ (~1 \le d_b, t_b, w_b \le 10^8~).

Другий рядок містить три цілі числа ~d_m~, ~t_m~ та ~w_m~ (~1 \le d_m, t_m, w_m \le 10^8~)

Третій рядок містить два цілі числа ~d_t~ та ~t_t~ (~1 \le d_t, t_t \le 10^8~).

Формат вихідних даних

Виведіть « Bus », якщо Петрик буде використовувати автобус, « Metro », якщо метро, « Taxi », якщо таксі (відповідь слід виводити без лапок).

Приклад вхідних даних

1 3 2
2 10 1
20 3

Приклад вихідних даних

Bus

Приклад вхідних даних

100 10 15
10 5 5
15 5

Приклад вихідних даних

Metro

Приклад вхідних даних

10 10 7
3 5 20
3 5

Приклад вихідних даних

Taxi

Пояснення

Коментар до першого приклада.

Час очікування автобуса становить 1 хвилину, поїздки 3 хвилини, а дороги від зупинки 2 хвилини, що дає в результаті 6 хвилин затрат на такий шлях.

Час очікування метро становить 2 хвилини, поїздки 10 хвилин, а дороги від зупинки 1 хвилину, що дає в результаті 13 хвилин затрат на такий шлях.

Час очікування таксі становить 20 хвилин, що вже перевищує затрати часу на інші варіанти транспорту.

Автобус є оптимальним видом транспорту по витратах часу у цьому випадку.

Коментар до другого приклада.

Аналогічно до минулого приклада, загальний час поїзки можна порахувати як суму часу очікування, часу поїздки та часу дороги до торвого центру. Для автобуса це значення дорівнює ~100+10+15=125~, для метро ~10+5+5=20~, а для таксі ~15+5=20~. У даному випадку оптимальними є метро та таксі, але оскільки метро дешевше за таксі, то Петрик обере метро.

Коментар до третього приклада.

Загальний час поїздки на автобусі становить ~10+10+7=27~, на метро ~3+5+20=28~, на таксі ~3+5=8~. Відповідно відповіддю є таксі як єдиний найшвидший вид транспорту.

«Треба було йти у біоінженерію»- опечалений програміст.

У зв'язку зі страхом після останніх скорочень в IT секторі Петрик хоче оцінити свою продуктивність. Він як стабільний працівник робить рівно одну робочу задачу за день, правда графік у нього специфічний: він працює ~a~ днів через ~b~ днів (тобто має ~a~ робочих днів поспіль та ~b~ вихідних після них).

Петрик, бувши прихильником теорії хаотичного відпочинку, не працює кожен ~n~-тий день, незалежно від того, чи є це робочим днем, чи вихідним. Проте, для компенсації, кожен ~m~-тий день, якщо він для Петрика робочий, то він працює удвічі ефективніше, тобто робить дві задачі за день.

Оцініть місячну продуктивність Петрика (скільки задач він зробить), якщо місяць має ~k~ днів та починається з першого робочого дня.

Формат вхідних даних

У першому рядку вказані п'ять цілих чисел ~a, b, n, m, k~ (~1 \le a, b, n, m, k \le 10^5~)

Формат вихідних даних

Виведіть єдине ціле число - продуктивність Петрика

Приклад вхідних даних

3 1 3 10 5

Приклад вихідних даних

3

Приклад вхідних даних

10 2 11 3 5

Приклад вихідних даних

6

Пояснення

У першому прикладі перші три дні для Петрика є робочими, проте в третій з них він не працює, бо ~n=3~. Четвертий день є вихідним за розкладом, а п'ятий день для Петрика є робочим. Оскільки ~m=10~, а у місяці всього ~5~ днів, то жоден день Петрик не працював подвійно. Таким чином сумарно Петрик працював три дні у звичайному темпі що дає відповідь у три задачі.

У другому прикладі Петрик циклічно працює ~10~ днів і ~2~ дні відпочиває, а день додаткового хаотичного відпочинку наступає ~11~ днем. Оскільки ~k=5~, то всі дні цього місяця будуть робочими за графіком, бо місяць закінчиться раніше ніж наступить якийсь вихідний. Також відомо що ~m=3~, а значить кожен третій день є днем подвійної ефективності. Тоді перші два дні Петрик працює у звичайному темпі та виконує дві задачі, третій день працює подвійно та виконує ще дві задачі, а після цього четвертий та п'ятий день він працює звичайно та виконує ще дві задачі. Тоді сумарно Петрик виконав ~2+2+2=6~ задач за цей місяць.

Поки Петрик ходив розважався у кіно — інші студенти активно вчились. Так, після хвилі ностальгії по старим часам, Даня з Діаною вирішили позмагатись у вирішенні двох останніх та улюблених ними задач із ЗНО з математики: стереометрії та параметра. Для обох студентів випадковим чином були згенеровані набори завдань. Таким чином Даня отримав ~n~ наборів задач по ~a_i~ задач в кожному, а Діана отримала ~m~ наборів задач по ~b_i~ в кожному. За умовами змагання, учасники мають послідовно розв'язувати свої набори завдань починаючи від першого.

Усе було б чудово, якби люди не мали фізичних обмежень, тож, на жаль, кожен з учасників має фіксовану максимальну ефективність ~e~, яка дорівнює кількості задач, яку той може зробити за одну годину. Крім того, втомлюючись люди починають думати повільніше, тому щогодини ефективність учасника зменшується рівно на ~1~, поки не дійде до нуля.

Щоб компенсувати цю несправедливість життя, кожен раз як учасник повністю вирішує набір задач, то він одразу наливає собі святковий келих "хербатки" (від пол. herbata, чай) та завдяки ньому відновлює свою ефективність до максимуму, а відлік години починається спочатку. Зверніть увагу, що якщо в цей момент мало відбутись зниження ефективності, то воно не відбувається. Переможцем змагання стає учасник, що розв'язав найбільшу кількість задач.

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

Формат вхідних даних

Перший рядок містить два цілі числа ~n, m~ (~1 \le n, m \le 2 \cdot 10^5~).

Другий рядок містить ~n~ цілих чисел ~a_i~ (~1 \le a_i \le 10^9~).

Третій рядок містить ~m~ цілих чисел ~b_i~ (~1 \le b_i \le 10^9~).

Четвертий рядок містить одне ціле число ~e~ (~1 \le e \le 10^9~)

Формат вихідних даних

У першому рядку виведіть ім'я переможця (« Danya » або « Diana ») або « Draw » у випадку нічиї.

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

Приклад вхідних даних

2 3
2 1
3 4 5
2

Приклад вихідних даних

Diana
6:3

Приклад вхідних даних

3 2
4 8 3
4 2
5

Приклад вихідних даних

Danya
15:6

Приклад вхідних даних

2 2
3 2
3 2
2

Приклад вихідних даних

Draw
5:5

Пояснення

У першому прикладі ефективність кожного учасника дорівнює ~2~. Тоді за першу годину Даня розв'яже перший набір з двох задач та вип'є чай для відновлення своєї ефективності до максимуму. Після цього за другу годину він розв'яже другий та останній для себе набір з однієї задачі, що дасть в сумі ~3~ розв'язані задачі.

У свою чергу Діна за першу годину розв'яже дві задачі, а за другу годину ще одну задачу, що завершить вирішення першого набору задач. Після цього поновивши енергію чаєм за третю годину буде вирішено 2 задачі з другого набору, за четверту годину 1 задача з другого набору та у зв'язку з спадом ефективності до нуля на цьому рішення задач цієї ночі буде завершене. Таким чином в сумі розв'язано ~6~ задач.

Успішно склавши сесію, Петрик збирається відправитись автівкою до своїх батьків у Кременчук, відстань до якого від університету рівна ~d~ кілометрів.

Машина Петрика не є новою, тому споживає цілих ~w~ літрів бензину кожен кілометр дороги. По дорозі до рідної домівки розміщено ~n~ заправок, кожна з яких пропонує пальне за ~c_i~ гривень за літр та розміщена на відстані ~x_i~ кілометрів від точки відправлення. Проте, на подив, кожна заправка пропонує свій унікальний вид бензину, які змішувати між собою в баку не можна.

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

Гарантується, що початково бак пустий та існує таке ~i~, що ~x_i = 0~.

Формат вхідних даних

Перший рядок містить два цілі числа ~d, w~ (~1 \le d, w \le 10^6~).

Другий рядок містить одне ціле число ~n~ (~1 \le n \le 10^3~).

Третій рядок містить ~n~ цілих чисел ~c_i~ (~0 \le c_i \le 10^6~).

Четвертий рядок містить ~n~ цілих чисел ~x_i~ (~0 \le x_i \le d~).

Гарантується, що існує таке ~i~, що ~x_i = 0~.

Формат вихідних даних

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

Система оцінки

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

1. (~20~ балів): ~n \leq 16~;
2. (~20~ балів): ~c_1 = c_2 = \dots = c_n~;
3. (~20~ балів): ~w=1~; ~d \leq 10^3~;
4. (~40~ балів): без додаткових обмежень.

Приклад вхідних даних

10 10
2
2 1
0 4

Приклад вихідних даних

60

Приклад вхідних даних

10 5
2
2 4
0 2

Приклад вихідних даних

50

Пояснення

У першому прикладі довжина дороги складає ~10~ кілометрів, а витрати пального дорівнюють ~10~ літрів на кілометр. Існує всього дві заправки: одна початкова з ціною ~2~ гривні за літр та одна на відстані ~4~ кілометри з ціною ~1~ гривня за літр. Оскільки у другій заправці ціна найдешевша, то буде оптимально заправитись мінімально на першій заправці щоб доїхати до другої. Тоді на першій заправці слід заправити ~4*10=40~ літрів бензину, а на другій заправити необхідні для проїзду залишку дороги ~6*10=60~ літрів бензину. Таким чином мінімальний розмір баку щоб така дорога була можливою становаить ~60~ літрів.

У другому прикладі довжина дороги складає ~10~ кілометрів, а витрати пального дорівнюють ~5~ літрів на кілометр. Існує всього дві заправки: одна початкова з ціною ~2~ гривні за літр та одна на відстані ~2~ кілометри з ціною ~4~ гривні за літр. Оскільки у першій заправці ціна найдешевша, то буде оптимально заправитись на ній до кінця дороги. Тоді на першій заправці слід заправити ~5*10=50~ літрів бензину, а на другій не заправлятись. Таким чином мінімальний розмір баку щоб така дорога була можливою становаить ~50~ літрів.

На екзамені з алгоритмів Петрик витягнув нещасливу задачу, тому вельми просить вашої допомоги. Перед вами стандартна шахова дошка ~8 \times 8~, клітинки якої пронумеровані зліва направо від ~a~ до ~h~ та знизу вгору від ~1~ до ~8~. Серед білих фігур дошці можуть бути всі види фігур, крім короля, а серед чорних навпаки — є лише один король. Також відомо що фігури розставлені абсолютно довільно, тобто їх розміщення може не підпорядковуватись стандартним правилам шахів (білі навіть можуть мати забагато фігур певного типу). Вашою задачею є визначити, у якому положенні знаходиться чорний гравець: мат, пат чи звичайне положення.

Довідка з шахів:

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

Правила ударів/ходів фігур в рамках задачі:

• Королева — б'є по вертикалях, діагоналях та горизонталях, на яких вона перебуває, але вона не може перескакувати через інші фігури.
• Тура — б'є по вертикалях та горизонталях, на яких вона перебуває, але не може перескакувати через інші фігури.
• Слон — б'є по діагоналях, на яких він перебуває, але не може перескакувати через інші фігури.
• Кінь — хід конем складається строго з двох пересувань: на одне поле по вертикалі чи горизонталі, потім віддаляючись від вихідного поля на одне поле по діагоналі. Це єдина фігура, яка може перескакувати через інші фігури.
• Пішак — б'є по діагоналі на одну клітинку в сторону суперника (таким чином білі пішаки завжди б'ють тільки по діагоналі вгору).
• Король — пересувається зі свого поля на одне з вільних суміжних полів (у тому числі й по діагоналі), що не перебуває під ударом фігур суперника. Може бити фігуру, яка знаходиться на суміжному полі, якщо вона не під ударом.

Формат вхідних даних

Вхідні дані містять ~8~ рядків, кожен з яких складається з ~8~ символів. Кожен символ задає відповідну клітинку шахової дошки:

• символ « . » позначає пусту клітинку
• символ « p » позначає пішака
• символ « r » позначає туру
• символ « n » позначає коня
• символ « b » позначає слона
• символ « Q » позначає королеву
• символ « K » позначає короля

Гарантується, що є рівно один король.

Формат вихідних даних

У випадку мату у першому рядку виведіть «Checkmate», а в наступних рядках виведіть клітинки всіх фігур, що завдають шах у довільному порядку.

У випадку пату у першому рядку виведіть «Stalemate».

В іншому випадку виведіть «Continue» та у довільному порядку всі клітинки, у які король може зробити хід.

Приклад вхідних даних

......K.
...r.pp.
......b.
pp..n.r.
....p...
.......p
...p.b.p
..Q..n..

Приклад вихідних даних

Continue
g7

Приклад вхідних даних

Kp......
p......r
........
.n......
........
........
p.pppppp
r.bQ.b..

Приклад вихідних даних

Stalemate

Приклад вхідних даних

r.......
.p...p.n
bbp.rp..
...KQr..
..p...r.
.p......
..p.pp..
...n....

Приклад вихідних даних

Checkmate
c4
e5

Приклад вхідних даних

........
......K.
.....ppp
........
........
........
........
..QQQQQQ

Приклад вихідних даних

Continue
f8
g8
h8

Пояснення

У першому прикладі король може атакувати пішака на ~g7~ та перейти туди, бо ця клітинка не перебуває під атакою жодної білої фігури.

Ілюстрація до першого приклада.

У другому прикладі король не знаходиться під шахом. У нього є три потенційно можливі ходи: ~b8~, ~b7~ та ~a7~. Хід на ~b8~ неможливий, бо це призведе до шаху від пішака на ~a7~. Хід на ~b7~ неможливий, бо це призведе до шаху від тури на ~h7~. Хід на ~a7~ неможливий, бо це призведе до шаху від тури на ~h7~. Таким чином король не перебуває під шахом, але здійнити хід не може, що означає пат.

Ілюстрація до другого приклада.

У третьому прикладі король знаходиться під шахом, спричиненим пішаком на ~c4~ та королевою на ~e5~. Крім того будь-який хід короля залишить його під шахом, що створює мат.

Ілюстрація до третього приклада.