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

Вхідні дані

Стандартний вхідний потік містить кілька (скільки саме – наперед невідомо, але не менше 1 й не більше 1000) рядків, кожен рядок містить по два числа, розділених пробілом. Значення самих чисел не перевищують за модулем мільярд (інакше кажучи, належать проміжку ~[-10^9; +10^9]~).

Результати

У стандартний вихідний потік потрібно вивести суму кожної пари чисел (кожну суму в окремому рядку).

Приклад

Вхід

2 3
17 25

Результат

5
42

Орієнтований зважений граф заданий переліком дуг (орієнтованих ребер). Відсортувати ці дуги за зростанням довжин, зберігши (додатковими полями) номери цих дуг у вхідних даних.

Вхідні дані

Перший рядок містить кількість вершин ~N~ (~2\leqslant N\leqslant 30000~) і кількість дуг (орієнтованих ребер) ~M~ (~1\leqslant M\leqslant 123456~). Кожен із подальших ~M~ рядків містить рівно три цілих числа ~u~, ~v~ та ~len~ – початок, кінець та довжину дуги. ~1\leqslant u, v\leqslant N~, ~u\neq v~, ~1\leqslant len\leqslant 10^9~. Гарантовано, що довжини всіх дуг різні.

Результати

Результат має містити ~M~ рядків по чотири цілих числа ~u~, ~v~, ~len~, ~idx~ у кожному – початок, кінець, довжину дуги, та її номер у вхідних даних (нумерація з одиниці). При цьому дуги мають бути відсортовані за зростанням довжин.

Приклад

Вхід

3 4
3 2 4
3 1 8
1 2 14
1 3 2

Результат

1 3 2 4
3 2 4 1
3 1 8 2
1 2 14 3

Примітки

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

Одного разу незграбна секретарка переплутала особові справи учнів. Тому їх потрібно знову впорядкувати спочатку по класам, а всередині класу по прізвищам.

Вхідні дані

У першому рядку задано число ~N~ (~1\leqslant N\leqslant 1000~) — кількість особових справ. Далі для кожного з ~N~ учнів такі дані (кожне у своєму рядку):

• прізвище
• ім'я
• клас
• дата народження

Прізвище та ім'я – рядки не більше ніж з 20 символів, клас – рядок, що складається з числа (від 1 до 11) та латинської літери (від "A" до "Z"), дата народження – дата у форматі ДД.ММ.РР. Гарантується, що всередині одного класу нема однопрізвищників.

Вихідні дані

У вихідний файл потрібно вивести ~N~ рядків, у кожному з яких записано дані для одного учня. Рядки повинні бути впорядковані спочатку по класам, а потім по прізвищам.

Приклад

Вхідні дані

3
Sidorov
Sidor
9A
20.07.93
Petrov
Petr
11B
23.10.92
Ivanov
Ivan
9A
10.04.93

Результати

9A Ivanov Ivan 10.04.93
9A Sidorov Sidor 20.07.93
11B Petrov Petr 23.10.92

Примітка

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

Напишіть програму, яка виконуватиме послідовність запитів виду ADD num, PRESENT num та COUNT (без параметра). Програму обов'язково слід писати за допомогою бібліотечного типу (колекції) set (її реалізації в конкретних мовах програмування можуть називатися HashSet, TreeSet, SortedSet, ...).

Виконання кожного запиту виду ADD num має додавати елемент num у множину (якщо такий елемент вже є, додавання ще однієї копії не змінює множину), на екран при цьому нічого не виводиться.

При виконанні кожного запиту виду PRESENT num має видаватися повідомлення YES або NO (великими літерами, в окремому рядку), відповідно до того, чи є такий елемент у множині; значення множини при цьому не змінюється.

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

Вхідні дані

У першому рядку задано кількість запитів ~N~ (~1\leqslant N\leqslant 10^5~), далі йдуть ~N~ рядків, кожен з яких містить по одному запиту згідно з описаним форматом.

Значення чисел є цілими і не перевищують за модулем 100 000 000 (інакше кажучи, належать проміжку ~[-10^8; +10^8]~).

Результати

Виводьте окремими рядками результати запитів PRESENT та COUNT; на запити ADD нічого не виводьте.

Приклади

Вхід

7
ADD 5
ADD 7
COUNT
PRESENT 3
PRESENT 5
ADD 3
COUNT

Результат

2
NO
YES
3

У банка є клієнти. Кожен клієнт має рівно один рахунок.

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

1. починається з числа 1, потім через пробіл іде ім'я клієнта (слово з латинських букв), далі через пробіл іде сума грошей, яка додається до рахунку поточного клієнта (ціле число, не перевищує за модулем ~10\,000~).
2. починається з числа 2, через пробіл іде ім'я клієнта. На кожен такий запит програма повинна відповісти, яка сума в даний момент є на рахунку заданого клієнта. Якщо таке ім'я клієнта поки що ні разу не згадувалося в запитах виду 1, виводьте замість числа слово ERROR.

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

Зверніть увагу, що у ситуації, коли клієнт зняв грошей сумарно рівно стільки ж, скільки поклав, сума на рахунку стає рівною 0; але, раз його ім'я вже зустрічалося, нульове значення не є підставою виводити ERROR.

Вхідні дані

Перший рядок вхідних даних – кількість запитів ~N~ (обмеження на максимальне значення ~N~ – приблизно до ~10^5=100\,000~).

Далі йдуть ~N~ рядків, у кожному з яких задано один запит одного з двох вищеописаних видів.

Результати

На кожний запит 2-го виду потрібно вивести поточне значення на рахунку заданого клієнта (або слово ERROR).

Приклади

Вхід

7
1 asdf 3
1 zxcv 5
2 asdf
1 asdf -2
2 asdf
2 lalala
2 zxcv

Результат

3
1
ERROR
5

Примітки

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

Один – з використанням бібліотечної словникової структури даних. Відповідна готова колекція чи контейнер може називатися (залежно від мови програмування) Dictionary, dict, map, HashMap, SortedMap, тощо.

Інший – із використанням власноруч написаних hash-таблиць (не використати бібліотечні, а написати спрощений їх аналог вручну, користуючись лише масивами та/або списками).

Знайдіть усі способи подати вказане натуральне ~N~ як суму двох квадратів (тобто, ~N=x^2+y^2~, де ~x~, ~y~ – цілі додатні).

Вхідні дані

Єдиний рядок містить єдине число ~N~ (~1\leqslant N\leqslant 10^{13}~).

Результати

Виведіть всі пари цілих додатних ~x~, ~y~, таких, що ~x^2+y^2=N~. Пари, де ~x~ та ~y~ лише переставлені місцями, слід вважати різними (при ~x\neq y~) й виводити кожну окремо. Перелік пар обов'язково повинен бути впорядкованим за зростанням ~x~.

Приклади

Вхід

16

Результат

Вхід

10

Результат

1 3
3 1

Вхід

4225

Результат

16 63
25 60
33 56
39 52
52 39
56 33
60 25
63 16

Примітки

1. Просять вивести лише розкладення в суму квадратів цілих додатних, тому в першому тесті нема й не можна виводити ні ~0^2+4^2~, ні ~4^2+0^2~. З тієї ж причини, у третьому тесті нема й не можна виводити ні ~0^2+65^2~, ні ~65^2+0^2~.

2. Якщо вказане ~N~ неможливо подати як ~x^2+y^2~, слід просто нічого не виводити. DMOJ налаштований так, що йому байдуже, чи це буде взагалі жодного байту, чи саме лише переведення рядка; але в будь-якому разі зайві видимі символи заборонені; зокрема, коли нема способів подати ~N~ як ~x^2+y^2~, виведення мусить не містити жодного видимого символу.

Напишіть програму, яка знаходитиме кількість натуральних чисел із проміжку ~[a; b]~, які задовольняють одночасно двом таким вимогам:

1. число є точним квадратом, тобто корінь з нього цілий (наприклад, точними квадратами є ~1=1^2~, ~9=3^2~, ~1024=32^2~; а 8, 17, 1000 не є точними квадратами);

2. сума цифр цього числа кратна ~K~ (Наприклад, сума цифр числа 16 рівна ~1+6=7~).

Програма повинна прочитати три числа в одному рядку ~a\,b\,K~ і вивести одне число – кількість чисел, які задовольняють умовам.

Обмеження:

~1\leqslant a\leqslant b\leqslant 2\cdot10^9~,

~2\leqslant K\leqslant 42~.

Вхід

17 222 9

Результат

3

Примітка

Цими трьома числами є 36, 81 і 144. Вивести треба лише кількість 3, але раптом комусь це допоможе зрозуміти, чому їх три…

Як відомо, простим називають таке натуральне число, яке має рівно два дільники – одиницю й самого себе. Перші десять простих чисел – 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Напишіть програму, яка знайде усі підряд, у порядку зростання, прості числа у проміжку від ~A~ до ~B~ (обидві межі включно).

Вхідні дані

У єдиному рядку через пробіл задані два натуральні числа ~A~ та ~B~, які є межами проміжку. Обмеження:

• ~1\leqslant A~;
• ~B\leqslant 10^{13}~;
• ~A\leqslant B\leqslant A+100~.

Результати

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

Приклади

Вхід

2 5

Результат

2
3
5

Вхід

4 4

Результат

У старих іграх можна зіткнутися з такою ситуацією. Персонаж стрибає по платформах, які висять у повітрі. Він повинен перебратися від одного краю екрана до іншого. При стрибку з платформи на сусідню, персонаж витрачає ~|y_2 - y_1|~ енергії, де ~y_1~ і ~y_2~ — висоти, на яких розташовані ці платформи. Крім того, є суперприйом, що дозволяє перескочити через платформу, але на це витрачається ~3\cdot|y_3 - y_1|~ енергії.

Звісно ж, енергію потрібно витрачати максимально економно, а Суперприйом можна використовувати будь-яку кількість разів (зокрема й не використовувати взагалі).

Вам відомі координати усіх платформ у порядку від лівого краю до правого. Знайдіть мінімальну кількість енергії, потрібну персонажу, щоб дістатись від першої платформи до останньої.

Вхідні дані

У першому рядку записана кількість платформ ~n~ (~1\leqslant n\leqslant 30000~). Другий рядок містить ~n~ натуральних чисел, які не перевищують 30000 – висоти, на яких розміщено платформи.

Результати

Виведіть єдине число – мінімальну кількість енергії, яку повинен витратити персонаж гри на подолання платформ.

Приклади

Вхід

3
1 5 10

Результат

9

Вхід

3
1 5 2

Результат

3

Задача в цілому аналогічна задачі «Структура (колекція) set» (і наполегливо рекомендується зробити спочатку її), але елементами повинні бути не числа, а дещо складніші об'єкти: прямокутники, кожен з яких описується довжинами двох своїх сторін a, b (два цілі числа) та кольором (string) col. Повертати прямокутники дозволено (b×a – те само, що a×b), а колір враховується. Інакше кажучи, елемент-прямокутник належить множині тоді й тільки тоді, коли множина містить елемент-прямокутник, в якого такі самі розміри, але порядок цих розмірів може бути хоч таким самим, хоч переставленим; при цьому колір повинен бути таким самим (у смислі звичайної case-sensitive рівності рядків).

Кожен із запитів ADD та/або PRESENT має по три параметри a b col, саме в такому порядку. Вони задаються в одному рядку через пробіли.

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

• ADD a b col
• PRESENT a b col
• COUNT (без параметрів).

Програму обов'язково слід писати за допомогою бібліотечного типу (колекції) set (її реалізації в конкретних мовах програмування можуть називатися HashSet, TreeSet, SortedSet, ...).

Виконання кожного запиту виду ADD a b col повинно додавати прямокутник до множини (якщо такий само прямокутник вже є, додавання ще однієї копії не змінює множину). На екран при цьому нічого не виводиться.

При виконанні кожного запиту виду PRESENT a b col має видаватися повідомлення YES або NO (великими літерами, в окремому рядку), відповідно до того, чи є такий елемент-прямокутник у множині; значення множини при цьому не змінюється.

При виконанні кожного запиту виду COUNT має видаватися на екран в окремому рядку кількість різних елементів-прямокутників у множині; значення множини при цьому не змінюється.

Вхідні дані

У першому рядку задано кількість запитів ~N~ (~5\leqslant N\leqslant 2\cdot10^5~), далі йдуть ~N~ рядків, кожен з яких містить по одному запиту згідно з описаним форматом. Всі параметри a та b є цілими числами від 1 до 1234567890. Всі параметри col є рядками, що містять від 1 до 15 латинських (англійських) літер, без будь-яких інших символів.

Результати

Виводьте окремими рядками результати запитів PRESENT (рівно одне YES чи NO великими буквами) та COUNT (рівно одне число); на запити ADD нічого не виводьте.

Приклади

Вхід

11
ADD 5 2 red
COUNT
PRESENT 5 2 red
PRESENT 5 2 ReD
PRESENT 2 5 red
ADD 2 5 green
COUNT
ADD 2 5 red
COUNT
ADD 5 2 red
COUNT

Результат

1
YES
NO
YES
2
2
2

Примітки

Перша відповідь 1 правильна, бо на той момент множина містить рівно один елемент-прямокутник 5 2 red.

Друга відповідь YES правильна, бо коли питають про наявність прямокутника, з такими самими розмірами 5 2 в такому ж порядку, причому такого самого кольору red, то він вже наявний.

Третя відповідь NO правильна, бо хоч розміри 5 2 такі самі в такому ж порядку, але колір інший (case-sensitive передбачає, що ReD не дорівнює red).

Четверта відповідь YES правильна, бо розміри 2 5 є тими самими числами (хоч і в іншому порядку), що й 5 2, і колір правильний.

П'ята відповідь 2 правильна, бо перед тим був запит ADD з елементом-прямокутником, що відрізняється від вже наявного кольором, тому тоді його додали, від чого кількість елементів множини змінилася.

Шоста відповідь 2 правильна, бо перед тим був запит ADD з елементом-прямокутником 2 5 red, що (незважаючи на переставляння місцями чисел) вважається рівним одному з уже наявних у множині прямокутників 5 2 red, тому множина не змінилася й продовжує містити рівно 2 елементи-прямокутники.

Сьома відповідь 2 правильна, бо перед тим був запит ADD з елементом-прямокутником, за всіма ознаками рівним вже наявному (найпершому) елементу-прямокутнику, тому множина не змінилася й продовжує містити рівно 2 елементи-прямокутники.

Абсолютно повне виконання завдання передбачає, що воно виконане і через бібліотечну колекцію HashSet (з написанням власних GetHashCode та Equals), і через бібліотечну колекцію SortedSet (з написанням власного компаратора). В разі виконання іншою мовою програмування, з'ясуйте відповідні деталі самостійно, але це повинен бути бібліотечний спосіб через хеш-таблиці та бібліотечний спосіб через дерева. Само собою, можна виконати частину, на відповідну частину балів.