Прямокутник, із сторонами паралельними осям координат, заданий координатами протилежних вершин: (~X_1,Y_1~) та (~X_2,Y_2~).

Знайдіть площу прямокутника.

Обмеження:

• ~0 \le X_1, Y_1, X_2, Y_2 \le 100~

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

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

Наступний рядок містить цілі числа ~X_2, Y_2~.

Числа у рядках розділяються пропуском.

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

У вихідний потік вивести відповідь.

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

0 0
10 10

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

100

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

10 0
0 10

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

100

Задається рядок ~S~ довжиною ~N~. Рядок ~S~ містить малі та великі літери англійського алфавіту.

Знайдіть кількість великих літер, які містяться в рядку ~S~.

Обмеження

• ~1 \le N \le 100~
• ~S~ містить лише малі та великі літери англійського алфавіту

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

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

Наступний рядок містить ~S~.

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

У вихідний потік вивести відповідь.

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

3
AbC

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

2

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

3
abc

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

0

На координатній площині задано ~N~ точок з цілими координатами (~X_i,Y_i~), де ~1 \le i \le N~.

Знайдіть порядковий номер точки з найбільшою абсцисою та найбільшою ординатою.

Якщо таких точок є декілька, то виведіть найменший порядковий номер.

Обмеження

• ~1 \le N \le 10^5~
• ~-10^6 \le X_i, Y_i \le 10^6~

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

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

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

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

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

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

4
0 0
1 1
-1 10
5 -10

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

4
3

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

5
10 10
0 10
20 0
15 10
20 0

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

3
1

Задається відсортований масив ~A~, який містить ~N~ цілих чисел та ціле число ~K~.

Ваше завдання знайти позицію(індекс) числа ~K~ в масиві ~A~. Відлік елементів починається з 0. Якщо число ~K~ відсутнє в масиві ~A~, то виведіть -1.

Обмеження

• ~1 \le N \le 10^7~
• ~1 \le A_i \le 10^9~
• ~1 \le K \le 10^9~

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

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

Наступний рядок містить ~N~ цілих чисел ~A_i~, які розділяються пропуском.

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

У вихідний потік вивести відповідь.

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

5 4
1 2 3 4 5

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

3

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

5 445
11 22 33 44 55

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

-1

Степан та його друзі грають у гру з водяними рушницями. Гравці поділилися на дві команди: перша команда має номери від 1 до 4, а друга - від 5 до 8.

Сьогодні Степан судить гру. За кожне влучання гравця команда отримує 100 балів. Якщо на протязі 10 с фіксується ще одне влучання цього ж гравця, то додатково нараховується 50 балів для його команди.

Степан ретельно записав час та влучні постріли обох команд і має проблему із підрахунком балів.

Допоможіть Степану порахувати бали команд.

Обмеження

• ~1 \le n \le 100~
• ~0 \le t_i \le 1000~
• ~1 \le a_i , b_i \le 8~

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

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

Кожен із наступних ~n~ рядків містить три цілі числа ~t_i , a_i , b_i~ - гравець ~a_i~ влучив в гравця ~b_i~ в момент часу ~t_i~ (у секундах).

Гравці ~a_i~ та ~b_i~ гарантовано належать до різних команд.

Проміжки часу ~t_i~ є різними і впорядкованими за зростанням.

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

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

Пояснення

Приклад 1.

На 10 с гравець 1 влучає в гравця 6 і перша команда отримує 100 балів.

На 20 с гравець 1 влучає у гравця 7 і перша команда отримує 100 балів. Оскільки це друге влучання гравця 1 на протязі 10 с, то його команда отримує додаткові 50 балів. Тепер перша команда має 250 балів.

На 21 с гравець 8 (команда 2) влучає у гравця 1 і друга команда отримує 100 балів.

Рахунок 250 - 100 на користь першої команди.

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

3
10 1 6
20 1 7
21 8 1

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

250 100

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

3
10 2 5
15 2 6
25 2 5

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

400 0

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

2
10 5 2
11 6 3

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

0 200

Дано рядок ~S~, який містить малі англійські символи.

Ваше завдання --- написати програму для видалення мінімальної кількості таких символів із рядка ~S~, щоб рядок став паліндромом. Порядок символів змінювати не дозволяється.

Обмеження

• ~1 \le |S| \le 10^3~, де ~|S|~ - довжина рядка
• ~S~ містить символи проміжку ['a'..'z']

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

Вхідний потік містить рядок ~S~.

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

У вихідний потік вивести відповідь - мінімальну кількість символів, які треба видалити з рядка ~S~ щоб утворився паліндром.

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

aebcbda

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

2

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

abbsa

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

1

~L~-knight(~a,b~) може переміститися з клітинки (~x_1,y_1~) в клітинку (~x_2,y_2~) де:

~x_2=x_1 \pm a~ і ~y_2=y_1 \pm b~

або

~x_2=x_1 \pm b~ і ~y_2=y_1 \pm a~

Наприклад, ~L~-knight(1,2) або ~L~-knight(2,1) з червоної клітинки може переміститися в будь-яку зелену.

Задається шахівниця розміром ~n \times n~. Дайте відповідь на запитання для кожної пари (~a,b~):

• Яка мінімальна кількість ходів потрібна для ~L~-knight(~a,b~), щоб перейти з позиції (0,0) в позицію (n-1,n-1)? Якщо ~L~-knight(a,b) не може дістатися до місця призначення, то виведіть -1.

Відповідь вивести для кожного ~L~-knight(~a,b~) згідно формату вихідних даних.

Обмеження

• ~5 \le n \le 25~
• ~1 \le a,b \le n~

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

Вхідний потік містить одне ціле число ~n~ - розмірність шахівниці.

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

У вихідний потік вивести ~n-1~ рядок. ~i~-й (де ~1 \le i \le n~) рядок містить ~n-1~ цілих чисел, розділених пропуском, які є мінімальною кількістю ходів для ~L~-knight(~i,j~) для відповідного ~j~ (де ~1 \le j \le n~) щоб перейти з позиції (0,0) в позицію (n-1,n-1).

Наприклад, для ~n=3~ вихідні дані для всіх пар (~i,j~) розтащуються таким чином:

(1,1) (1,2)
(2,1) (2,2)

Примітка

Приклади можливих варіантів ходів для різних ~(i,j)~:

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

5

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

4 4 2 8 
4 2 4 4 
2 4 -1 -1 
8 4 -1 1

Існує неорієнтований граф з ~N~ вершинами, пронумерованими від 1 до ~N~, кількість ребер на початку рівна 0.

Обробіть ~Q~ запитів у порядку їх слідування. Після обробки кожного запиту виведіть кількість вершин, які не з'єднані ребром з іншими вершинами.

~I~-й запит ~q_i~ належить до одного з двох наступних типів:

-- 1 ~u~ ~v~: з'єднати вершину ~u~ і вершину ~v~ ребром. Гарантується, що коли задається цей запит, вершина ~u~ та вершина ~v~ не з'єднані ребром.

-- 2 ~v~: видаліть усі ребра, які з'єднують вершину ~v~ та інші вершини. (Сама вершина ~v~ не видаляється.)

Обмеження

• ~2 \le N \le 3 \cdot 10^5~
• ~1 \le Q \le 3 \cdot 10^5~
• Для кожного запиту першого типу ~1 \le u,v \le N~ і ~u \neq v~.
• Для кожного запиту другого типу ~1 \le v \le N~.
• Безпосередньо перед подачею запиту першого типу між вершинами ~u~ і ~v~ немає ребра.
• Усі значення у вхідних даних є цілими числами.

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

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

Наступні ~Q~ рядків містять запити ~q_i~.

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

У вихідний потік вивести ~Q~ рядків. В ~i~-му рядку ~(1 \le i \le Q)~ має бути записано кількість вершин, які не з'єднані ребром з іншими вершинами.

Пояснення

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

Після першого запиту вершина 1 і вершина 2 з'єднані одна з одною ребром, але вершина 3 не з'єднана з іншими вершинами. Таким чином, 1 виводимо в першому рядку.

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

Четвертий запит просить видалити всі ребра, які з'єднують вершину 1 та інші вершини, зокрема, видалити ребро між вершиною 1 і вершиною 2, а також між вершиною 1 і вершиною 3. У результаті вершина 2 і вершина 3 з'єднані одна з одною, тоді як вершина 1 не з'єднана ребром з іншими вершинами. Таким чином, виводимо 0 і 1 в третьому і четвертому рядках відповідно.

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

3 7
1 1 2
1 1 3
1 2 3
2 1
1 1 2
2 2
1 1 2

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

1
0
0
1
0
3
1

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

2 1
2 1

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

2