\begin{problem}{Merge. Слияние последовательностей}{merge.in}{merge.out}{2 секунды}

Даны две бесконечные неубывающие последовательности $A$ и $B$. 
Требуется найти $k$-ый элемент в неубывающей последовательности $C$, 
содержащей все элементы из $A$ и $B$ (включая повторы).

Последовательность $A$ задается с помощью полинома $P(x) = x^3$:
$$a_1 = P(1) \bmod 12345, ~~~ a_i = a_{i-1} + (P(i) \bmod 12345) \mbox{, при } i > 1$$

Последовательность $B$ задается с помощью полинома $Q(x) = x^2$:
$$b_1 = Q(1) \bmod 123, ~~~ b_i = b_{i-1} + (Q(i) \bmod 123) \mbox{, при } i > 1$$

\InputFile

Входной файл содержит натуральное число $k$ ($1 \le k \le 10^7$).

\OutputFile

В выходной файл выведите одно число --- ответ на задачу. Гарантируется, что 
ответ не превышает $2 \cdot 10^9$.

\Example

\begin{example}
\exmp{
1
}{
1
}%
\exmp{
3
}{
5
}%
\end{example}

\end{problem}
