Igor 喜欢十六进制表示法,并且认为十六进制表示法中的正整数如果每个数字和每个字母出现不超过 t 次就很有趣。例如,如果 t = 3,则整数 13a13322、aaa、abcdef0123456789 是有趣的,但数字 aaaa、abababab 和 1000000 是不有趣的。
你的任务是找到 Igor 感兴趣的第 k 个最小的十六进制整数。整数不应包含前导零。
输入
第一行包含两个整数 k 和 t (1 ≤ k ≤ 2·109, 1 ≤ t ≤ 10) — 所需整数的个数以及某个整数或字母在感兴趣的整数中出现的最大次数。
可以证明,对于此类约束,答案总是存在。
输出
以十六进制表示法打印 Igor 的第 k 个最小有趣整数的唯一整数。
示例
输入 #1
17 1
输出 #1
12
输入 #2
1000000 2
输出 #2
fca2c
注意
如果 t = 1,则前 20 个有趣的整数:1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, 10, 12, 13, 14, 15。因此第一个示例的答案等于 12。