#2665. [cqoi2012]编号

内存限制:128 MiB 时间限制:3 Sec

题目描述

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

输入格式

第一行为整数k
 

输出格式

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

样例

样例输入


			
20

样例输出


			
0001321

数据范围与提示


















编号



1-3



4-7



8-10



k



<=200



<=10000



<=200000