Contest Duration: - (local time) (100 minutes) Back to Home
D - String Equivalence /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

この問題では、英小文字からなる文字列のみを考えます。

• |s| = |t| である。
• 任意の i, j に対し次のいずれかが成立する。
• s_i = s_j かつ t_i = t_j
• s_i \neq s_j かつ t_i \neq t_j

たとえば、abcaczyxzx は同型ですが、abcacppppp は同型ではありません。

• 任意の s と同型な文字列 t に対し、s \leq t が成立する。ただしここで \leq は辞書順での比較を表す。

たとえば、abcac は標準形ですが、zyxzx はそれより辞書順で小さい　abcac と同型のため標準形ではありません。

### 制約

• 1 \leq N \leq 10
• 入力は全て整数である。

### 入力

N


### 出力

w_1
:
w_K


### 入力例 1

1


### 出力例 1

a


### 入力例 2

2


### 出力例 2

aa
ab


Score : 400 points

### Problem Statement

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

Strings s and t are said to be isomorphic when the following conditions are satisfied:

• |s| = |t| holds.
• For every pair i, j, one of the following holds:
• s_i = s_j and t_i = t_j.
• s_i \neq s_j and t_i \neq 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 when the following condition is satisfied:

• For every string t that is isomorphic to s, s \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 N. Print all strings of length N that are in normal form, in lexicographically ascending order.

### Constraints

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

### Input

Input is given from Standard Input in the following format:

N


### Output

Assume that there are K strings of length N that are in normal form: w_1, \ldots, w_K in lexicographical order. Output should be in the following format:

w_1
:
w_K


### Sample Input 1

1


### Sample Output 1

a


### Sample Input 2

2


### Sample Output 2

aa
ab