[cqoi2012]编号

你需要给一批商品编号，其中每个编号都是一个 $7$ 位 $16$ 进制数（由 09、af 组成）。为了防止在人工处理时不小心把编号弄错，要求任意两个编号至少有三个位置对应的数字不相同。

第一个编号为 0000000，第二个编号为不违反上述规定的前提下最小的编号，依此类推：每次分配一个新编号时，总是选择不和前面编号冲突的最小编号（注意编号都是 $16$ 进制数，可以比较大小）。

按此规律，前面若干个编号分别是：

0000000, 0000111, 0000222, ..., 0000fff, 0001012, 0001103, 0001230, 0001321, 0001456, ...

输入 $k$，你的任务是求出第 $k$ 小的编号。

输入格式

第一行为整数 $k$。

输出格式

输出第 $k$ 小的编号（字母必须输出小写）。输入保证这个编号存在。

样例输入

20

样例输出

0001321

数据范围

• 测试点 $1\sim 3$：$k\le 200$；
• 测试点 $4\sim 7$：$k\le 10^4$；
• 测试点 $8\sim 10$：$k\le 2\times 10^5$。

来源与许可

本题为 CQOI 2012 试题「编号」，题面与测试数据整理自 BZOJ 2665。

样例 1

输入

20

输出

0001321