For each integer i from 1 to n, you must print a string s_i of length n consisting of lowercase Latin letters. The string s_i 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 : s_i” where s_i is one of possible strings. Otherwise, print “i : NO”.