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