16548번 - Unique Substrings 스페셜 저지다국어

문제

Create a string of N lowercase letters S₁S₂ . . . S_N where 1 ≤ N ≤ 2¹². The string should have exactly K unique substrings.

A substring is the sequence of letters of the form S_LS_L+1 . . . S_R−1S_R for some 1 ≤ L ≤ R ≤ N. Two substrings are the same if they are the same sequence of letters.

입력

Line 1 contains one integer K (1 ≤ K ≤ 2²²). N is not given; the string that you create may have any number of letters N as long as 1 ≤ N ≤ 2¹².

출력

Print one line with one string of N lowercase letters where 1 ≤ N ≤ 2¹². It should have exactly K unique substrings. If there are multiple such strings, any will be accepted. It can be proven that such a string always exists with the given constraints of N and K.

제한

힌트

For the first example, the 15 unique substrings of banana are a, an, ana, anan, anana, b, ba, ban, bana, banan, banana, n, na, nan and nana. Another string that has 15 unique substrings is aaaaaaaaaaaaaaa which would also be a correct output for the first example.