[CQOI2012] 编号

题目描述

你需要给一批商品编号,其中每个编号都是一个 $7$ 位 $16$ 进制 数(由 $0$ 至 $9$, $a$ 至 $f$ 组成)。 为了防止在人工处理时不小心把编号弄错,要求任意两个编号至少有三个位置对应的数字不相同。 第一个编号为 $0000000$,第二个编号为不违反上述规定的前提下最小的编号,…,每次分配一个新编号时,总是选择不和前面编号冲突的最小编号(注意到编号都是 $16$ 进制数,可以比较大小)。 按此规律,前面若干编号分别是: $$0000000,0000111,0000222,…,0000fff,0001012,0001103,0001230,00 01321,0001456,…$$ 输入 $k$,你的任务是求出第 $k$ 小的编号。

输入输出格式

输入格式


一行一个数,为整数 $k$。

输出格式


输出第 $k$ 小的编号(字母均为小写)。输入保证这个编号存在。

输入输出样例

输入样例 #1

20

输出样例 #1

0001321

说明

对于 15% 的数据,$k \leq 200$; 对于 35% 的数据,$k \leq 10000$; 对于 60% 的数据,$k \leq 200000$。 对于 100% 的数据,$k \leq 1048576$。