Hexadecimal Code Allocation with Minimum Hamming Distance

You are given a task to assign identification codes to a set of products. Each code is a 7-digit hexadecimal number (using digits 0-9 and letters a-f). To ensure that the codes are not easily mistaken when handled manually, any two codes must differ in at least 3 positions (i.e. their Hamming distance is at least 3).

The codes are assigned in increasing order. The first code is 0000000. For every subsequent code, the smallest hexadecimal number (in lexicographical/numerical order) that does not violate the rule with any of the previously assigned codes is chosen.

For example, the first few codes are:

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

Given an integer k, your task is to output the k-th smallest valid code in this sequence. (Note: the first code corresponds to k = 1.)

inputFormat

The input consists of a single integer k indicating the position of the desired valid code.

Constraints: It is guaranteed that k is small enough for a greedy algorithm to finish in time.

outputFormat

Output the k-th valid 7-digit hexadecimal code (with lowercase letters) that satisfies the minimum Hamming distance condition, padding with leading zeros if necessary.

sample

1

0000000