CF747F.Igor and Interesting Numbers

Igor likes hexadecimal notation and considers positive integer in the hexadecimal notation interesting if each digit and each letter in it appears no more than t times. For example, if t = 3, then integers 13a13322, aaa, abcdef0123456789 are interesting, but numbers aaaa, abababab and 1000000 are not interesting.

Your task is to find the k-th smallest interesting for Igor integer in the hexadecimal notation. The integer should not contain leading zeros.

伊戈尔喜欢十六进制表示法，并认为一个正整数的十六进制表示是“有趣的”，当且仅当其中每个数字和每个字母出现的次数均不超过 $t$ 次。例如，若 $t = 3$，则整数 13a13322、aaa、abcdef0123456789 是有趣的；但 aaaa、abababab 和 1000000 不是有趣的。

你的任务是找出伊戈尔所定义的第 $k$ 小的“有趣的”十六进制整数。该整数不得包含前导零。

The first line contains the two integers k and t (1 ≤ k ≤ 2·109, 1 ≤ t ≤ 10) — the number of the required integer and the maximum number of times some integer or letter can appear in interesting integer.

It can be shown that the answer always exists for such constraints.

第一行包含两个整数 $k$ 和 $t$（$1 \leq k \leq 2 \cdot 10^9$，$1 \leq t \leq 10$）—— 分别表示所要求的整数的序号，以及“有趣整数”中某个数字或字母最多可出现的次数。

可以证明，在给定约束下，答案总是存在。

Print in the hexadecimal notation the only integer that is the k-th smallest interesting integer for Igor.

以十六进制表示法输出 Igor 的第 k 个最小的“有趣整数”。

The first 20 interesting integers if t = 1: 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, 10, 12, 13, 14, 15. So the answer for the first example equals 12.

当 $t = 1$ 时，前 20 个有趣的整数为：1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, 10, 12, 13, 14, 15。因此第一个样例的答案为 12。