Марсохід, який здійснює міжнародну місію на Марсі, несправний. Для відновлення його працездатності необхідно підвищити потужність його батареї. Потужність батареї марсохода задається цілим додатним числом. Поточна потужність батареї дорівнює ~a~, для відновлення працездатності марсохода необхідно підвищити її потужність до значення ~b~. Для зміни потужності батареї на марсохід з Землі можна передавати спеціальні сигнали двох типів: ~X~ і ~Y~. Сигнал типу ~X~ збільшує поточну потужність батареї на 1, а сигнал типу ~Y~ збільшує поточну потужність батареї на 2. Організатори місії хотіли б змінити потужність батареї до необхідної, передавши мінімальну кількість сигналів. На жаль, через особливості пристрою марсохода, якщо потужність батареї виявляється кратна цілому числу ~c~, він остаточно виходить з ладу і перестає реагувати на сигнали.

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

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

Вхідні дані містять три цілих числа: ~a~, ~b~ і ~c~, по одному у рядку (~1 \le a < b \le 10^9~, ~2 \le c \le 10^9~, ~a~ не кратне ~c~, ~b~ не кратне ~c~).

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

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

Примітка

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

У першому прикладі можна діяти в такий спосіб: відправити на марсохід сигнали Y, X, Y. Потужність батареї змінюється наступним чином: 2 - 4 - 5 - 7.

У другому прикладі можна діяти в такий спосіб: відправити на марсохід сигнали X, Y, X, Y. Потужність батареї змінюється наступним чином: 4 - 5 - 7 - 8 - 10.

Оцінювання

Підзадача 1: 25 балів, ~1 \le a < b \le 15, 2 \le c \le 15~

Підзадача 2: 25 балів, ~1 \le a < b \le 10^5, 2 \le c \le 10^5~

Підзадача 3: 25 балів, ~1 \le a < b \le 10^9, c = 2~

Підзадача 4: 25 балів, ~1 \le a < b \le 10^9, 2 \le c \le 10^9~

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

2
7
3

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

3

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

4
10
3

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

4

Вчені планують провести важливий експеримент з використанням дослідного модуля на планеті X-2019. В процесі експерименту буде проведено два вимірювання: основне та контрольне. Кожне вимірювання займає рівно одну годину і має починатися через ціле число годин після початку роботи дослідницького модуля. Дані експерименту планується негайно передати на орбітальну станцію. Канал зв'язку з орбітальною станцією буде встановлений з ~l~-ї по ~r~-у годину від початку роботи дослідного модуля, включно. Крім того, згідно з планом експерименту між вимірюваннями планета повинна зробити ціле число обертів навколо своєї осі. Планета X-2019 здійснює оберт навколо своєї осі за ~a~ годин. Таким чином, якщо вимірювання здійснюються на ~i~-й та ~j~-й годині, то повинна виконуватися нерівність ~l \le i < j \le r~, а величина (~j - i~) повинна бути кратна ~a~. Тепер вченим необхідно зрозуміти, скільки існує різних способів провести вимірювання.

Потрібно написати програму, яка за заданими межами часу вимірювань ~l~ і ~r~ та періодом обертання планети навколо своєї осі ~a~ визначає кількість можливих способів провести вимірювання: кількість пар цілих чисел ~i~ та ~j~, таких що ~l \le i < j \le r~, і величина (~j - i~) кратна ~a~.

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

Вхідні дані містять три цілих числа, по одному на рядку: ~l~, ~r~ і ~a~ (~1 \le l < r \le 10^9~, ~1 \le a \le 10^9~).

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

Виведіть одне ціле число: кількість способів провести вимірювання.

Примітка

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

У першому прикладі можна провести вимірювання в наступні пари годин: (1, 3), (1, 5), (2, 4), (3, 5).

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

Оцінювання

Підзадача 1: 30 балів, ~1 \le l < r \le 100, 1 \le a \le 100~;

Підзадача 2: 30 балів, ~1 \le l < r \le 10^5, 1 \le a \le 10^5~;

Підзадача 3: 40 балів, ~1 \le l < r \le 10^9, 1 \le a \le 10^9~,

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

1
5
2

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

4

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

4
9
6

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

0

З метою пошуку закономірностей іноді корисно згенерувати довгу послідовність по визначених правилах. Відомо, наприклад, що послідовність 0, 0+1, 0+1+3, 0+1+3+5,. . . , 0+1+3+. . . + (2n - 1),. . ., складена з сум декількох перших непарних натуральних чисел, складається з квадратів цілих чисел: 0, 1, 4, 9,. . . , ~N^2~,. . ..

Узагальнимо цю послідовність наступним чином: будемо використовувати замість початкового значення не нуль, а число k. Отримаємо послідовність: k, k+1, k+1+3, k+1+3+5, . . . , k+1+3+. . . +(2n-1),. . .. На відміну від випадку k = 0, в цій послідовності можуть зустрічатися не тільки повні квадрати. Необхідно знайти мінімальне ціле невід'ємне число, квадрат якого зустрічається в цій послідовності.

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

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

У єдиному рядку міститься ціле число k - початкове число в послідовності (~-10^{12} \le k \le 10^{12}~).

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

Виведіть мінімальне невід'ємне ціле число, квадрат якого зустрічається в описаній послідовності. Якщо в послідовності не зустрічається квадратів цілих чисел, виведіть «none».

Примітка

У першому прикладі кожне число послідовності є повним квадратом. Мінімальне з них - 0, ~0^2~ = 0.

У другому прикладі послідовність починається так: -5, -4, -1, 4, 11, 20,. . .. Мінімальне невід'ємне ціле число, квадрат якого зустрічається в послідовності - 2, ~2^2~ = 4.

У третьому прикладі послідовність починається так: 2, 3, 6, 11, 18,. . .. У ній немає квадратів цілих чисел.

Оцінювання

Підзадача 1: 7 балів, ~0 \le k \le 1000~;

Підзадача 2: 10 балів, ~0 \le k \le 10^5~,

Підзадача 3: 27 балів, ~0 \le k \le 10^{12}~,

Підзадача 4: 7 балів, ~-1000 \le k \le 1000~,

Підзадача 5: 10 балів, ~-10^5 \le k \le 10^5~,

Підзадача 6: 39 балів, ~-10^{12} \le k \le 10^{12}~,

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

0

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

0

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

-5

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

2

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

2

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

none

В академії фізичної культури розробили новий метод інтервальних тренувань спортсменів. Відповідно до цього методу спортсмен повинен тренуватися щодня, проте зростання навантаження повинно постійно змінюватися його зменшенням і навпаки. План тренування являє собою набір цілих додатних чисел ~a_1, a_2,. . . , a_m~, де ~a_i~ описує навантаження спортсмена в ~i~-й день. Будь-які два сусідніх дні повинні мати різне навантаження: ~a_i \neq a_{i + 1}~. Щоб зростання навантаження і його зменшення чергувалися, для ~i~ від 1 до ~m - 2~ має виконуватися така умова: якщо ~a_i < a_{i + 1}~, то ~a_{i + 1} > a_{i + 2}~, якщо ж ~a_i > a_{i + 1}~, то ~a_{i + 1} < a_{i + 2}~.

Сумарне навантаження в процесі виконання плану повинне складати ~n~, тобто ~a_1 + a_2 +. . . + A_m = n~. Обмеження на кількість днів у плані немає, ~m~ може бути будь-яким, але навантаження в перший день тренувань зафіксоване: ~a_1 = k~. Перш ніж приступити до тестування нового методу, керівництво академії хоче з'ясувати, скільки різних планів тренувань задовольняє описаним обмеженням.

Потрібно написати програму, яка за заданими ~n~ і ~k~ визначає, скільки різних планів тренувань задовольняють описаним обмеженням, і виводить залишок від ділення кількості таких планів на числа ~10^9 + 7~.

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

У першому рядку вхідних даних знаходяться цілі числа ~n~, ~k~ (~1 \le n \le 5000~, ~1 \le k \le n~).

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

Виведіть одне число: залишок від ділення кількості планів тренувань на ~10^9 + 7~.

Примітка

У першому прикладі підходять наступні плани: [2, 1, 2, 1], [2, 1, 3], [2, 3, 1], [2, 4].

У другому прикладі єдиний план [3].

Scoring

Підзадача 1: 23 бали, ~1 \le n \le 10~;

Підзадача 1: 20 балів, ~1 \le n \le 30~,

Підзадача 1: 23 бали, ~1 \le n \le 500~,

Підзадача 1: 34 бали, ~1 \le n \le 5000~,

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

6 2

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

4

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

3 3

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

1

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

Тепер організатори повинні вибрати, хто з кандидатів відправиться в експедицію. Вирішено було вибрати учасників експедиції так, що якщо туди входить деякий кандидат ~i~, і ~a_i \neq -1~, то туди не входить кандидат ~a_i~. Організатори хочуть вибрати максимальну кількість учасників експедиції.

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

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

У першому рядку вхідних даних знаходиться ціле число ~n~ - кількість кандидатів (~1 \le n \le 300 000~).

У наступних ~n~ рядках дано результати опитування, ~i~-й з цих рядків містить результат опитування ~i~-го кандидата, ціле число ~a_i~ (~a_i = -1~ або ~1 \le a_i \le n~, ~a_i \neq i~).

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

У єдиному рядку виведіть одне ціле число - максимальну кількість кандидатів, яких можна відправити в експедицію.

Scoring

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

Підзадача 1: 19 балів, ~n \le 20~;

Підзадача 2: 10 балів, ~a_1 = -1~, для ~i > 1~ виконано ~a_i = i - 1~;

Підзадача 3: 15 балів, для всіх ~i~ виконано ~a_i < i~,

Підзадача 4: 13 балів, ~1 \le n \le 2000~,

Підзадача 5: 43 бали, ~1 \le n \le 300 000~,

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

4
2
4
2
1

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

2

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

3
2
-1
2

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

2