Ви знайшли секретний форум лідерів команди "Відбій". Звичайно ж, щоб увійти на форум, потрібно правильно відповісти на ключове питання. Відповідь на секретне питання - \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}.