F. Игорь и интересные числа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Игорь очень любит 16-ричную систему счисления и считает целое положительное число в 16-ричной системе счисления интересным, если каждая цифра и буква в нём встречается не более t раз. Например, если t = 3, то числа 13a13322, aaa, abcdef0123456789 — интересные, а числа aaaa, abababab и 1000000 — нет.

Перед вами стоит задача найти k-е по счёту интересное для Игоря число в 16-ричной системе счисления. Число не должно содержать лидирующих нулей.

Входные данные

В первой строке следует два целых числа k и t (1 ≤ k ≤ 2·109, 1 ≤ t ≤ 10) — номер искомого числа и максимальное число раз, которое может встречаться цифра или буква в интересном числе.

Можно показать, что при таких ограничениях ответ всегда существует.

Выходные данные

Выведите единственное целое число в 16-ричной системе счисления, которое является k-м по счёту интересным для Игоря числом в 16-ричной системе счисления.

Примеры
Входные данные
17 1
Выходные данные
12
Входные данные
1000000 2
Выходные данные
fca2c
Примечание

Первые 20 чисел, которые является интересными, если t = 1: 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, 10, 12, 13, 14, 15. Поэтому ответ на первый пример равен 12.