684. String Equivalence
0
Hard
Strings
s and
t are considered isomorphic if the following conditions are met:
∣s∣=∣t∣.
For any pair
i,j, one of the following must be true:
s[i]=s[j] and t[i]=t[j]. For example, abcac and zyxzx are isomorphic, while abcac and ppppp are not.
A string *s* is said to be in normal form if the following condition is satisfied:
For every string
t that is isomorphic to s, s≤t. Here ≤ represents lexicographic comparison. For example, abcac is in normal form, but zyxzx is not since it is isomorphic to abcac, which is lexicographically smaller than zyxzx.
You are given an integer N. Print all strings of length N that are in normal form, in lexicographically ascending order.
Input Format
The first line contains N.
Output Format
Print all strings of length N that are in normal form.
Example
Input
2
Output
aa
ab
Constraints
1<= N <= 10
Loading...
View Submissions
Console