#include<pthread.h>
#include<stdint.h>
#include<stdio.h>
#include<stdlib.h>
#include<stdarg.h>
#include<math.h>
#include<string.h>

struct node { struct node *t[6]; };
typedef struct node node;

node *r, *cr, *p;
int i, j, s, k, l, x, pos, a_o, lim, mot[1000000], b;
char mode[100], name[100];
FILE *out;

node *new_node(){
 p = (node*)malloc(sizeof(node));
 for(x = 0; x < a_o; x++) p->t[x] = 0;
 return p;
}

int** load(char *name){
 FILE *in = fopen("morphisms.txt", "r");
 char ch[3000];
 int **tmp = (int**)malloc(10*sizeof(int*));
 for(fgets(ch, 2000, in); strcmp(name, ch); fgets(ch, 2000, in), ch[strlen(ch)-1] = 0);
 for(fgets(ch, 2000, in), i = 0; strcmp(ch, "\n"); fgets(ch, 2000, in), i++){
  tmp[i] = (int*)malloc((strlen(ch)+1)*sizeof(int));
  j = 0;
  if(*ch != 'e') for(; ch[j]; j++) tmp[i][j] = ch[j]-'0';
  tmp[i][j] = -1;
 }
 fclose(in);
 return tmp;
}//*/

int* apply(int** mor, int* w, int l){
 int *tmp = (int*)malloc(l*sizeof(int));
 for(i = k = 0; k < l; i++) for(j = 0; (s = mor[w[i]][j]) >= 0 && k < l; j++) tmp[k++] = s;
 return tmp;
}//*/

int* fp(int** mor, int l){
 int *tmp = (int*)malloc(l*sizeof(int));
 for(*tmp = i = k = 0; k < l; i++) for(j = 0; (s = mor[tmp[i]][j]) >= 0 && k < l; j++) tmp[k++] = s;
 return tmp;
}//*/

node *get_cr(){
 p = r;
 for(x = 0; x < i; x++) p = p->t[mot[x]];
 return p;
}

void check(int* m, int lim){
 r = new_node();
 for(k = 0; k < lim-l; k++) for(i = 0, cr = r; i < l; i++){
  if(!cr->t[j = m[k+i]]) cr->t[j] = new_node();
  cr = cr->t[j];
 }
 sprintf(name, "%s_mor_%d_%d.txt", mode, lim, l);
 out = fopen(name, "wt");
 for(*mot = i = 0; i >= 0;)
  if(get_cr()->t[mot[i]])
   if(i == l-1){
    for(j = 0; j <= i; j++) fprintf(out, "%d", mot[j]); fprintf(out, "\n");
    here: while(mot[i] == a_o-1) i--;
    if(i >= 0) mot[i]++;
   }else mot[++i] = 0;
  else goto here;
 fprintf(out, "\n");
 close(out);
}

void usage(){
 printf("Usage: mor mode lim l\n");
 exit(0);
}

int main(int ac, char **av){
 if(ac != 4) usage();
 sprintf(mode, "%s", av[1]);
 lim = atoi(av[2]);
 l = atoi(av[3]);
  if(!strcmp(mode, "f5")){a_o = 5; check(fp(load("f5"), lim), lim);}//4n+1
   else if(!strcmp(mode, "m1")){ a_o = 3; check(apply(load("m1"), fp(load("f5"), lim), lim), lim); }//4n-2 n>=2
   else if(!strcmp(mode, "m2")){ a_o = 3; check(apply(load("m2"), fp(load("f5"), lim), lim), lim); }//4n-2 n>=2
   else if(!strcmp(mode, "g8")){ a_o = 2; check(apply(load("g8"), fp(load("f5"), lim), lim), lim);}//4n-6 n>=3
   else if(!strcmp(mode, "g12")){ a_o = 2; check(apply(load("g12"), fp(load("f5"), lim), lim), lim);}//4n-6 n>=3
   else if(!strcmp(mode, "g14")){ a_o = 2; check(apply(load("g14"), fp(load("f5"), lim), lim), lim);}//4n-1 n>=11
   else if(!strcmp(mode, "aabbcc")){ a_o = 2; check(apply(load("aabbcc"), fp(load("f5"), lim), lim), lim);}//4n+4 n>=6
  else if(!strcmp(mode, "f3")){ a_o = 3; check(fp(load("f3"), lim), lim); }
   else if(!strcmp(mode, "g11")){ a_o = 2; check(apply(load("g11"), fp(load("f3"), lim), lim), lim);}
   else if(!strcmp(mode, "g3")){ a_o = 2; check(apply(load("g3"), fp(load("f3"), lim), lim), lim);}
   else if(!strcmp(mode, "aabbcabba")){ a_o = 2; check(apply(load("aabbcabba"), fp(load("f3"), lim), lim), lim);}
  else usage();
}