1. Згортка

Максимальна оцінка: 100 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 64 MБ
Вхідний файл: convol.in
Вихідний файл: convol.out
Програма: convol.*

Згорткою кортежу (a₁; a₂; ... ; a_k) називають таку суму добутків:

Послідовність додатних чисел {a_j} задано таким чином: згортка перших j членів дорівнює 4 ^j – 1. Легко впевнитись, що ця послідовність починається так: 1, 2, 6, 20, 70.

Завдання
Обчислити a_N  за даним N.

Вхідні дані
Єдиний рядок файлу містить число N, де 0 < N < 2000. Принаймні у половині тестів N < 200.

Вихідні дані
Єдиний рядок файлу містить цілу частину a_N.
Приклади

2. Комарі

Максимальна оцінка: 100 балів
Обмеження на час: 0,5 сек.
Обмеження на пам’ять: 64 МБ
Вхідний файл: mosquito.in
Вихідний файл: mosquito.out
Програма: mosquito.*

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

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

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

Вхідні дані
Перший рядок вхідних даних містить невід’ємне ціле число N — кількість комарів на стелі. Наступні N рядків містять пари невід'ємних цілих чисел x_j і y_j — координати j-го комара на стелі. Останній (N + 2)-ий рядок містить 2 натуральних числа w і h — лінійні розміри підручника.

В усіх тестах N ≤ 10⁵, max{x_j, y_j} ≤ 10⁹, max{w, h} ≤ 10⁹.
В 70% тестів N ≤ 10⁴, max{x_j, y_j} ≤ 10⁴.
В 50% тестів N ≤ 10³, max{x_j, y_j} ≤ 10³.

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

Приклади

3. Пірати й золото

Максимальна оцінка: 100 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: pirat.in
Вихідний файл: pirat.out
Програма: pirat.*

Команда з N піратів знайшли скарб з M однакових золотих монет і хоче його розділити. Всі пірати мають різний вік, при чому пірат з номером j + 1 старший за пірата з номером j. Першим пропозицію, про те як поділити скарб висуває найстарший пірат. Він вказує, скільки золотих монет має отримати кожен учасник команди. Якщо цю пропозицію підтримує не менше половини всіх піратів, то її приймають, і гроші розподіляють відповідним чином. Інакше найстаршого з живих пірата вбивають, а скарб ділять між собою вже N – 1 пірат за таким самим принципом. Кожен пірат (перераховано у порядку важливості):

• хоче вижити;

• хоче отримати максимальну кількість монет;

• жадібний і голосує за будь-яку пропозицію тоді й лише тоді, коли він впевнений, що інакше його вб’ють або він отримає менший зиск;

• мислить логічно й повністю передбачає хід думок будь-якого іншого пірата щодо розподілу грошей;

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

Завдання
За відомими N і M визначте, скільки монет отримає кожний пірат.

Вхідні дані
В єдиному рядку файлу записано два цілих числа: N і M (1 ≤ N ≤10000, 0 ≤ M ≤ 1 000 000 000).

Вихідні дані
Файл містить N рядків по одному цілому числу в кожному рядку. У j-му рядку потрібно записати кількість монет, які отримає j-ий пірат. Якщо j-го пірата вб’ють, то в j-му рядку потрібно записати число –1.

Приклади