Вы нашли секретный форум лидеров команды "Отбой". Конечно же, чтобы войти на форум, надо правильно ответить на ключевой вопрос. Ответ на секретный вопрос - \textbf{k}-ое по счёту красивое число на отрезке от \textbf{l} до \textbf{r} (нумерация с единицы). Напомним, что число \textbf{x} называется \textit{красивым}, если сумма его цифр делится на \textbf{n}. Торопитесь, у вас есть всего две секунды на то, чтобы ответить на секретный вопрос, иначе вас рассекретят и выгонят из команды. \InputFile В единственной строке входного файла заданы четыре числа \textbf{l}, \textbf{r}, \textbf{n}, \textbf{k} (\textbf{1} ≤ \textbf{l} ≤ \textbf{r} ≤ \textbf{10^18}, \textbf{1} ≤ \textbf{n} ≤ \textbf{1000},\textbf{1} ≤ \textbf{k} ≤ \textbf{10^18}). \OutputFile В выходной файл выведите \textbf{k}-ое красивое число на отрезке от \textbf{l} до \textbf{r}. Если такого числа не существует, то выведите \textbf{-1}.