Your company has received the contract to implement the new telephone system on the moon, where all telephone numbers will have 7 hexadecimal digits (see notes). The distance between two telephone numbers is the number of corresponding digits that differ. For example, the distance between 1b100fa and 11b0ffa is 3, because the 2nd, 3rd, and 5th digits (counting from the left) are different. In order to avoid wrong numbers, every pair of telephone numbers will have a distance of at least separation between them. Your policy for allocating telephone numbers is simple: each time a new number is required, the smallest possible number is assigned such that these conditions are preserved.
Your company is going to award a special prize to the person who is assigned the kth telephone number (k is 1-based). Return this number as a string of exactly 7 hexadecimal digits: '0' - '9' and lowercase 'a' - 'f'. The constraints guarantee that k is small enough for the prize to be awarded before it becomes impossible to allocate new numbers. |