Злиття послідовностей#5196
Увійти

Злиття послідовностей

1 секунда
64 мегабайти
Середня

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

Послідовність визначається за допомогою многочлена P(x) = x^3 наступним чином:

a_1 = P(1) \bmod 12345,\quad a_i = a_{i-1} + (P(i) \bmod 12345),\quad \text{для } i > 1

Послідовність визначається за допомогою многочлена Q(x) = x^2 наступним чином:

b_1 = Q(1) \bmod 123,\quad b_i = b_{i-1} + (Q(i) \bmod 123),\quad \text{для } i > 1

Вхідні дані

Вхідний файл містить одне ціле число (1 \leq k \leq 10^7).

Вихідні дані

Виведіть одне ціле число — відповідь на задачу. Гарантується, що відповідь не перевищує 2 \cdot 10^9.

Приклади

Приклад 1

Loading
Loading