Description

You need to assign numbers to a batch of products, where each number is a $7$-digit hexadecimal number (composed of $0$ to $9$, $a$ to $f$).

To prevent mistakes during manual processing, any two numbers must differ in at least three corresponding positions.

The first number is $0000000$, the second is the smallest number that does not violate the above rule, … Each time a new number is assigned, always choose the smallest number that does not conflict with the previous numbers (note that the numbers are hexadecimal, so they can be compared by value).

Following this rule, the first few numbers are:

$$0000000,0000111,0000222,…,0000fff,0001012,0001103,0001230,0001321,0001456,…$$

Given $k$, your task is to find the $k$-th smallest number.

Input Format

One integer $k$ on a single line.

Output Format

Output the $k$-th smallest number (letters must be lowercase). The input guarantees that this number exists.

20

0001321

Hint

For 15% of the testdata, $k \leq 200$;

For 35% of the testdata, $k \leq 10000$;

For 60% of the testdata, $k \leq 200000$.

For 100% of the testdata, $k \leq 1048576$.

Translated by ChatGPT 5