Даны две бесконечные неубывающие последовательности 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.