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

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

Examples

Input

1


Output

a


Input

2


Output

aa
ab
import java.util.Arrays;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {
	public static boolean nextPermutation(int[] a) {
		for (int i = a.length - 1; i > 0; --i) {
			if (a[i - 1] < a[i]) {
				int swapIndex = find(a[i - 1], a, i, a.length - 1);
				int temp = a[swapIndex];
				a[swapIndex] = a[i - 1];
				a[i - 1] = temp;
				Arrays.sort(a, i, a.length);
				return true;
			}
		}
		return false;
	}

	// destより大きい要素の中で最小のもののインデックスを二分探索で探す
	private static int find(int dest, int[] a, int s, int e) {
		if (s == e) {
			return s;
		}
		int m = (s + e + 1) / 2;
		return a[m] <= dest ? find(dest, a, s, m - 1) : find(dest, a, m, e);
	}

	static void listup(int arr[], Set<String> result, int N) {
		int perm[] = new int[N];
		int idx = 0;
		for (int a = 0; a < arr.length; ++a) {
			for (int j = 0; j < arr[a]; ++j) {
				if(arr[a] == 1){
					perm[idx++] = -1;
				}else{
					perm[idx++] = a;					
				}
			}
		}
		do {
			StringBuilder sb = new StringBuilder();
			int map[] = new int[arr.length];
			Arrays.fill(map, -1);
			int m = 0;
			for (int i = 0; i < perm.length; ++i) {
				int v = perm[i];
				if(v < 0){
					char c = (char) ('a' + m);
					m++;
					sb.append(c);
				}else{
					if (map[v] < 0) {
						map[v] = m;
						m++;
					}
					char c = (char) ('a' + map[v]);
					sb.append(c);					
				}
			}
			result.add(sb.toString());
			// System.out.println(Arrays.toString(perm)+" "+sb);
		} while (nextPermutation(perm));
	}

	static void rec(int N, int K, int[] arr, int i, int up, Set<String> result,
			int L) {
		if (K == 0) {
			if (N == 0) {
//				System.out.println(Arrays.toString(arr));
				listup(arr, result, L);
			}
			return;
		}
		for (int u = up; u <= N; ++u) {
			arr[i] = u;
			rec(N - u, K - 1, arr, i + 1, u, result, L);
			arr[i] = 0;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		Set<String> result = new TreeSet<String>();
		for (int K = 1; K < N; ++K) {
			// System.out.println(K);
			int arr[] = new int[K];
			rec(N, K, arr, 0, 1, result, N);
		}
		// K == N
		String sb = "";
		for(int i = 0 ; i < N ; ++i){
			sb = sb + (char)('a' + i);
		}
		result.add(sb);
//		System.out.println(result.size());
		for (String r : result) {
			System.out.println(r);
		}
	}
}
