510. Distinct Substrings

Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

A well-known application of suffix trees is solving the following problem: given a string, find the number of distinct substrings that the string has. For example, the string "abac" has 9 distinct substrings: "a", "b", "c", "ab", "ba", "ac", "aba", "bac", "abac".

You are faced with generating testcases for this problem.

More specifically, you should find the shortest string consisting only of lowercase English letters that has exactly the given amount n of distinct substrings. Among several shortest strings, choose the lexicographically smallest one.

Input
First and only line of the input file contains an integer n, 1 ≤ n ≤ 300.

Output
In the only line of the output file write the sought string.

Example(s)
sample input
sample output
5
aab




Online Contester Team © 2002 - 2010. All rights reserved.