Задано дві нескінчечнні неспадаючі послідовності A та B. Потрібно знайти k-тй елемент у неспадаючій послідовності C, яка містить усі елементы з A та B (включаючи повтори).
Послідовність A задається при допомозі полінома P(x) = x^3:
a_1 = P(1) mod 12345, a_i = a_{i-1} + (P(i) mod 12345), при i > 1
Послідовність B задається при допомозі полінома Q(x) = x^2:
b_1 = Q(1) mod 123, b_i = b_{i-1} + (Q(i) mod 123), при i > 1
Вхідний файл містить натуральне число k (1 ≤ k ≤ 10^7).
У вихідний файл виведіть одне число - відповідь до задачі. Гарантується, що відповідь не перевищує 2·10^9.