eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

Напомним, что число x называется красивым, если сумма его цифр делится на n. Торопитесь, у вас есть всего две секунды на то, чтобы ответить на секретный вопрос, иначе вас рассекретят и выгонят из команды.

Giriş verilənləri

В единственной строке входного файла заданы четыре числа l, r, n, k (1lr10^18, 1n1000,1k10^18).

Çıxış verilənləri

В выходной файл выведите k-ое красивое число на отрезке от l до r. Если такого числа не существует, то выведите -1.

Nümunə

Giriş verilənləri #1
1 10 1 1
Çıxış verilənləri #1
1