Тайни команди "Відбій"

Ви знайшли секретний форум лідерів команди "Відбій". Звичайно ж, щоб увійти на форум, потрібно правильно відповісти на ключове питання. Відповідь на секретне питання - k-те по рахункуу красиве число на відрізку від l до r (нумерація з одиниці).

Нагадаємо, що число x називається красивим, якщо сума його цифр ділиться на n. Поспішіть, у вас є усього дві секунди на те, щоб відповісти на секретне питання, інакше вас розсекретять і виженуть з команди.

Вхідні дані

У єдиному рядку вхідного файлу задано чотири числа l, r, n, k (1 ≤ l ≤ r ≤ 10^18, 1 ≤ n ≤ 1000, 1 ≤ k ≤ 10^18).

Вихідні дані

У вихідний файл виведіть k-те красиве число на відрізку від l до r. Якщо такого числа не існує, то виведіть -1.

Приклади