Задача J. Jump to number ≡

Условие

Требуется найти k-е по порядку q-ичное число (начиная с 1-го), сумма цифр которого равна n, а длина не превосходит l.

Формат входных данных

Во входных данных записаны четыре целых числа: q, n, l и k.

Формат выходных данных

Выходные данные должны содержать полученное число.

Если такого числа нет, либо оно выходит за пределы допустимого диапазона,
выходные данные следует оставить пустыми.

Ограничения

2 ≤ q ≤ 10, 1 ≤ (n, l) ≤ 4000, 1 ≤ k ≤ 10¹⁸

Примеры тестов

10 100 12 1

199999999999

2 1 1 2