Стіна покрита квадратною плиткою зі стороною ~M~ см. На стіну повісили картину. Відомі координати лівого нижнього кута картини, її ширина і висота. Визначте кількість плиток, які виявилися частково або повністю закриті картиною.

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

Перший рядок вхідних даних містить число ~M~ - сторону плитки. Другий і третій рядки містять числа ~X~ і ~Y~ - координати лівого нижнього кута картини. Четвертий і п'ятий рядки містять числа ~W~ і ~H~ - ширину і висоту картини. Вісь ~OX~ спрямована вправо, вісь ~OY~ - вгору. Лівий нижній кут однієї з плиток знаходиться на початку координат.

Всі числа цілі, не перевищують ~2 \cdot 10^9~, числа ~M~, ~W~, ~H~ - додатні, числа ~X~ і ~Y~ - додатні або дорівнюють 0.

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

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

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

10
15
5
35
20

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

12

Один давньоримський торговець брав декілька разів позику в банку. Кожен раз банкір записував розмір виданої позики на аркуші пергаменту, використовуючи римські числа. Але з огляду на дорожнечу пергаменту запис проводився щільно і всі числа виявилися записаними підряд, без роздільників. Коли торговець прийшов повертати позику, виявилося, що неможливо встановити розбиття запису на числа.

Наприклад, якщо на пергаменті записаний рядок «XIIV», його можна розбити на римські числа різними способами: XI + IV = 11 + 4 = 15 або XII + V = 12 + 5 = 17. Можливі й інші варіанти розбиття.

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

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

Програма отримує на вхід рядок, довжина якого не перевищує 250 символів. Рядок складається тільки з великих латинських літер I, V, X, L, С, D, M.

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

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

Примітка

Римськими цифрами можна записати цілі числа від 1 до 3999. Число представляється у вигляді суми тисяч, сотень, десятків і одиниць. Далі з наступної таблиці береться по одному елементу, що відповідають тисячам, сотням, десяткам, одиницям в такому порядку.

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

XIIV

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

15

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

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

Перший рядок вхідного потоку містить чотири числа ~x1,y1,x2,y2~, де (~x1,y1~) координати лівого нижнього кута прямокутника, а (~x2,y2~) координати правого верхнього кута прямокутника.

Другий рядок містить координати другого прямокутника в аналогічному форматі.

Третій рядок містить координати третього непрозорого прямокутника у тому ж форматі.

Всі координати лежать в межах від -1000 до 1000.

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

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

Примітка

До прикладу 1:

У прикладі 5 одиниць площі видно першого прямокутника і 12 одиниць площі другого.

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

1 2 3 5
6 0 10 4
2 1 8 3

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

17

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

Професор під час заліку дозволив Назару відкинути бали ~K~ (~1 \le K \le N-2~) перших задач перед оцінюванням. Яку кількість задач має відкинути Назар, щоб отримати максимальну оцінку за алгоритмом професора?

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

Єдиний рядок вхідного потоку містить ціле число ~N~ (~3 \le N \le 100000~) - кількість задач.

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

Вивести по одному у рядку всі можливі значення ~K~ у зростаючому порядку, при яких Назар отримає максимальну оцінку.

Примітка

До прикладу 1:

Якщо відкинути перші 2 оцінки, то залишиться 9,2,7. Відкинемо 2 і отримаємо середню оцінку 8 балів. Це є максимальна оцінка.

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

5
3 1 9 2 7

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

2

У Бориса та Іллі є по N поштових марок. Кожна із 2N марок має свою цінність на думку Бориса та цінність на думку Іллі.

Борис хоче віддати одну з марок Іллі. Якщо Ілля отримає марку від Бориса, то він має віддати одну із своїх марок Борису. Щоб не бути ні скупим, ні щедрим, Ілля постарається вибрати марку, як мінімум, таку ж цінну (на думку Іллі), як він отримав, але не більше, ніж на D одиниць ціннішу. Така марка може не існувати і тоді Ілля буде почувати себе нещасним.

Якщо Ілля віддасть марку взамін, то Борис аналогічно постарається віддати Іллі марку, як мінімум таку ж по цінності (на думку Бориса), але не більше, ніж на D одиниць ціннішу. Якщо такої марки не знайдеться, то Борис почуватиметься нещасним.

Такий цикл триватиме поки це можливо, або поки один із хлопців не отримає марку з цінністю 0. В цьому випадку хлопці будуть почуватися щасливими.

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

Кожна із ~N~ марок може бути вибрана Борисом, як початковий подарунок для Іллі. Визначити мінімальну кількість марок, які можуть бути подаровані так, щоб обидва хлопці були щасливими.

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

Перший рядок містить цілі числа ~N~, ~D~ (~1 \le N \le 10^5~, ~0 \le D \le 10^9~). Наступні ~2N~ рядків містять по два цілих числа, розділених пропуском, які відповідно позначають цінність марки по критеріях Бориса та Іллі. Перші ідуть ~N~ марок Бориса, а наступні ~N~ - марки Іллі. Гарантується, що величини цінності марок знаходяться в інтервалі [~0,10^9~].

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

Вивід містить ~N~ рядків. Рядок ~i~ містить одне ціле число: мінімальну кількість марок, які можуть бути подаровані при щасливій кінцівці, якщо Борис почне з марки ~i~. Якщо ж щаслива кінцівка при початку з марки ~i~ неможлива, то слід вивести -1.

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

2 1
1 1
5 0
4 2
1 4

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

3
1