Тайны команды "Отбой"

Вы нашли секретный форум лидеров команды "Отбой". Конечно же, чтобы войти на форум, надо правильно ответить на ключевой вопрос. Ответ на секретный вопрос - 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.

Примеры