Задано дві нескінчечнні неспадаючі послідовності \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}.