Тайни команди "Відбій"#4265
Ви знайшли секретний форум лідерів команди "Відбій". Звичайно ж, щоб увійти на форум, потрібно правильно відповісти на ключове питання. Відповідь на секретне питання - -те по рахунку красиве число на відрізку від до (нумерація з одиниці).
Нагадаємо, що число називається красивим, якщо сума його цифр ділиться на . Поспішіть, у вас є усього дві секунди на те, щоб відповісти на секретне питання, інакше вас розсекретять і виженуть з команди.
У єдиному рядку вхідного файлу задано чотири числа , , , (1 \leq l \leq r \leq 10^{18}, 1 \leq n \leq 1000, 1 \leq k \leq 10^{18}).
У вихідний файл виведіть -те красиве число на відрізку від до . Якщо такого числа не існує, то виведіть .
Приклад 1