atcoder#PANASONIC2020D. String Equivalence

String Equivalence

Score : 400400 points

Problem Statement

In this problem, we only consider strings consisting of lowercase English letters.

Strings ss and tt are said to be isomorphic when the following conditions are satisfied:

  • s=t|s| = |t| holds.
  • For every pair i,ji, j, one of the following holds:- si=sjs_i = s_j and ti=tjt_i = t_j.
    • sisjs_i \neq s_j and titjt_i \neq t_j.
  • si=sjs_i = s_j and ti=tjt_i = t_j.
  • sisjs_i \neq s_j and titjt_i \neq t_j.

For example, abcac and zyxzx are isomorphic, while abcac and ppppp are not.

A string ss is said to be in normal form when the following condition is satisfied:

  • For every string tt that is isomorphic to ss, sts \leq t holds. Here \leq denotes 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 NN. Print all strings of length NN that are in normal form, in lexicographically ascending order.

Constraints

  • 1N101 \leq N \leq 10
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN

Output

Assume that there are KK strings of length NN that are in normal form: w1,,wKw_1, \ldots, w_K in lexicographical order. Output should be in the following format:

w1w_1

::

wKw_K

1
a
2
aa
ab