Problem Description

You are a super hacker. You have targeted Takahashi as your attack subject and have discovered the following facts about Takahashi's computer password:

• It has a length of $ N $ characters.
• It only contains the characters a, b, and c.

Let's list all possible strings that could be Takahashi's computer password.

Input Format

The input is given from the standard input in the following format:

$ N $

• The first line contains the length of the password $ N $ ($ 1 $ $ ≦ $ $ N $ $ ≦ $ $ 8 $).

Output Format

Output all strings that satisfy both conditions in the problem statement, one per line, in lexicographical order.
See the notes for the definition of "lexicographical order".
Ensure there is a newline after the last string. Uppercase and lowercase letters are distinguished.

Sample Input and Output

Sample Input #1

1

Sample Output #1

a
b
c

Sample Input #2

2

Sample Output #2

aa
ab
ac
ba
bb
bc
ca
cb
cc

Notes/Hints

Sample Explanation 2

(※) For different strings $ s $ and $ t $ of the same length consisting of lowercase English letters, $ s $ is lexicographically earlier than $ t $ if the following condition is met; otherwise, $ s $ is lexicographically later than $ t $. - There exists an integer $ i $ ($ 1 $ $ ≦ $ $ i $ $ ≦ $ $ |s| $ $ = $ $ |t| $) such that the first $ i-1 $ characters (inclusive) of $ s $ and $ t $ are identical, but the $ i $th character is different, and the $ i $th character of $ s $ comes earlier in the alphabet. For example, cab**a**c is lexicographically earlier than cab**c**a ($ i $ $ = $ $ 4 $ satisfies the condition).

见题面 Input 部分

见题面 Output 部分