For each integer i from 1 to n, you must print a string si of length n consisting of lowercase Latin letters.
The string si must contain exactly i distinct palindrome substrings.
Two substrings are considered distinct if they are different as strings.
The input contains one integer n (1 ≤ n ≤ 2000).
You must print n lines. If for some i, the answer exists, print it in the form “i : si” where si is one of possible strings.
Otherwise, print “i : NO”.
1 : NO
2 : NO
3 : abca
4 : bbca
Problem Author: Mikhail Rubinchik
Problem Source: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014