class ListeDeMots{
    String contenu;
    ListeDeMots suivant;

    ListeDeMots(String c, ListeDeMots s){
	contenu = c;
	suivant = s;
    }

    static ListeDeMots creerDepuisTableau(String[] args){
	// initialiser a null ne pose pas de probleme.
	ListeDeMots l = null;
	for (int i = args.length-1; i >= 0; i--)
	    l = new ListeDeMots(args[i], l);
	return l;
    }


    // pour les 3 fonctions qui suivent, le test d'arret est (l == null)
    static void afficher(ListeDeMots l){
	if (l == null)
	    System.out.println();
	else{
	    System.out.print(l.contenu + " ");
	    afficher(l.suivant);
	}
    }

    static String concatener(ListeDeMots l){
	if (l == null)
	    return "";
	else
	    return l.contenu + concatener(l.suivant);
    }

    static int longueur(ListeDeMots l){
	if (l == null)
	    return 0;
	else
	    return 1 + longueur(l.suivant);
    }

    // partie 2

    static ListeDeMots recopierPremiers(ListeDeMots l, int n){
	if (n <= 0)
	    return null;
	if (l == null)
	    return null;
	return new ListeDeMots(l.contenu, recopierPremiers(l.suivant, n-1));
    }

    static ListeDeMots recopierAPartirDe(ListeDeMots l, int n){
	if (l == null)
	    return null;
	if (n == 1)
	    return new ListeDeMots(l.contenu, recopierAPartirDe(l.suivant, n));
	return recopierAPartirDe(l.suivant, n-1);
    }

    static ListeDeMots fusion(ListeDeMots s1, ListeDeMots s2){
	if (s1 == null)
	    return s2;
	if (s2 == null)
	    return s1;
	if (s1.contenu.compareTo(s2.contenu) < 0)
	    return new ListeDeMots(s1.contenu, fusion(s1.suivant, s2));
	else
	    return new ListeDeMots(s2.contenu, fusion(s2.suivant, s1));
    }

    static ListeDeMots trier(ListeDeMots l){
	int s = longueur(l);
	if (s <= 1)
	    return l;
	int t = s/2;
	
	ListeDeMots m1 = recopierPremiers(l, t);
	ListeDeMots m2 = recopierAPartirDe(l, t+1);
	return fusion(trier(m1), trier(m2));
    }
}


class ListeCirculaire{
    char contenu;
    ListeCirculaire suivant;

    ListeCirculaire(char c){
	contenu = c;
	suivant = this;
    }

    static boolean estSingleton(ListeCirculaire l){
	if (l == null)
	    return false;
	return l.suivant == l;
    }

    static ListeCirculaire inserer(char c, ListeCirculaire l){
	if (l != null){
	    ListeCirculaire tmp = new ListeCirculaire(l.contenu);
	    l.contenu = c;
	    tmp.suivant = l.suivant;
	    l.suivant = tmp;
	    return l;
	}
	else 
	    return new ListeCirculaire(c);
    }

    static void afficher(ListeCirculaire l){
	if (l == null)
	    return;
	ListeCirculaire m = l; // on sauvegarde le point de depart pour effectuer le test d'arret
	// cette idee est utilisee plusieurs fois dans la suite
	do{
	    System.out.print(m.contenu + " ");
	    m = m.suivant;
	} while (m != l);
	System.out.println();
    }

    static ListeCirculaire creerDepuisChaine(String c){
	ListeCirculaire l = null;
	for (int i = c.length()-1; i >= 0 ; i--)
	    l = inserer(c.charAt(i), l);
	return l;
    }

    static String creerChaine(ListeCirculaire l){
	String s = "";
	if (l == null)
	    return s;
	ListeCirculaire m = l;
	do{
	    s = s + m.contenu;
	    m = m.suivant;
	} while (m != l);
	return s;
    }

    // facile !
    static ListeCirculaire avancer(ListeCirculaire l){
	if (l == null)
	    return null;
	return l.suivant;
    }
}

class Lyndon{
    // on separe les 2 tests
    static boolean estCyclique(ListeCirculaire l){
	if (l == null || ListeCirculaire.estSingleton(l))
	    return false;
	ListeCirculaire m = l.suivant;
	String s0 = ListeCirculaire.creerChaine(l);
	do{
	    String s = ListeCirculaire.creerChaine(m);
	    if (s.equals(s0))
		return true;
	    m = m.suivant;
	} while (m != l);
	return false;
    }

    static boolean estMinimum(ListeCirculaire l){
	if (l == null || ListeCirculaire.estSingleton(l))
	    return true;
	ListeCirculaire m = l.suivant;
	String s0 = ListeCirculaire.creerChaine(l);
	do{
	    String s = ListeCirculaire.creerChaine(m);
	    if (s.compareTo(s0) < 0)
		return false;
	    m = m.suivant;
	} while (m != l);
	return true;
    }

    static boolean estLyndon(String s){
	ListeCirculaire l = ListeCirculaire.creerDepuisChaine(s);
	return (!estCyclique(l) && estMinimum(l));
    }

    // enumeration recursive
    static String[] tousLesMots(char[] alphabet, int taille){
	if (taille == 0)
	    return new String[]{""};
	String[] tmp = tousLesMots(alphabet, taille-1);
	String[] out = new String[tmp.length*alphabet.length];
	int j = 0;
	for(int i = 0; i < alphabet.length; i++)
	    for (int k = 0; k < tmp.length; k++){
		out[j] = tmp[k] + alphabet[i];
		j++;
	    }
	return out;
    }

    static String[] tousLesLyndon(char[] alphabet, int taille){
	String[] tmp = tousLesMots(alphabet, taille);
	int nb = 0;
	for (int i = 0; i < tmp.length; i++)
	    if (estLyndon(tmp[i]))
		nb++;
	String[] out = new String[nb];
	nb = 0;
	for (int i = 0; i < tmp.length; i++)
	    if (estLyndon(tmp[i])){
		out[nb] = tmp[i];
		nb++;
	    }
	return out;
    }

    static String concatenation(char[] alphabet, int taille){
	ListeDeMots l = null;
	for (int i = 1; i <= taille; i++){
	    if (taille%i == 0){
		String[] m = tousLesLyndon(alphabet, i);
		ListeDeMots mm = ListeDeMots.creerDepuisTableau(m);
		mm = ListeDeMots.trier(mm);
		ListeDeMots.afficher(mm);
		l = ListeDeMots.fusion(mm, l);
	    }
	}
	return ListeDeMots.concatener(l);
    }

    // vrai ssi s est un prefixe de t
    static boolean estPrefixe(String s, String t){
	if (t.length() < s.length())
	    return false;
	for(int i = 0; i < s.length(); i++)
	    if (s.charAt(i) != t.charAt(i))
		return false;
	return true;
    }

    static boolean verification(char[] alphabet, int taille){
	String chaine = concatenation(alphabet, taille);
	if (chaine.length() != (int)(Math.pow(alphabet.length, taille)))
	    return false;

	String[] mots = tousLesMots(alphabet, taille);
	ListeCirculaire l = ListeCirculaire.creerDepuisChaine(chaine);

	// on cherche si tous les mots sont presents
	for(int i = 0; i < mots.length; i++){
	    ListeCirculaire m = l;
	    boolean test = false;
	    do{
		test = test || estPrefixe(mots[i], ListeCirculaire.creerChaine(m));
		m = m.suivant;
	    } while (m != l);
	    if (test == false)
		return false;
	}
	return true;
    }
}