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

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

node *r, *p, *q;
int i, j, w5[1000000], f[1000000], z[50000];

node *new_node(){
 q = (node*)malloc(sizeof(node));
 q->t[0] = q->t[1] = q->t[2] = q->t[3] = q->t[4] = 0;
 return q;
}

int search(int *m, int l){//checks whether m[0..l-1] is in the tree
 int x;
 p = r;
 for(x = 0; x < l; x++) if(!(p = p->t[m[x]])) return 0;
 return 1;
}
  
void rec(node *c, int lvl){
 int x;
 if(!c) return;
 for(x = 0; x < lvl-1; x++){// loops over the lvl-1 conjugates of z[0..lvl-1]
  z[lvl+x] = z[x];
  if(!search(z+x+1, lvl)) break;
 }
 if(x == lvl-1 && lvl >= 2) printf("No !!!!\n"); //every conjugate of z[0..lvl-1] is in the tree
 for(z[lvl] = 0; z[lvl] < 5; z[lvl]++) rec(c->t[z[lvl]], lvl+1);
}

int main(){
 for(*f = i = j = 0; j < 100000; i++) switch(f[i]){ //constructs the fixed point of 01/2/03/24/23
  case 0: f[j++] = 0; f[j++] = 1; break;
  case 1: f[j++] = 2; break;
  case 2: f[j++] = 0; f[j++] = 3; break;
  case 3: f[j++] = 2; f[j++] = 4; break;
  case 4: f[j++] = 2; f[j++] = 3; break;
 }
 for(*w5 = i = j = 0; j < 100000; i++) switch(f[i]){ //constructs the prefix of w5
  case 0: w5[j++] = 0; w5[j++] = 1; w5[j++] = 2; w5[j++] = 3; break;
  case 1: break;
  case 2: w5[j++] = 4; w5[j++] = 0; w5[j++] = 2; w5[j++] = 3; break;
  case 3: w5[j++] = 1; w5[j++] = 4; w5[j++] = 2; w5[j++] = 3; break;
  case 4: w5[j++] = 1; w5[j++] = 4; break;
 }
 r = new_node();
 for(i = 0; i < 90000; i++) for(p = r, j = i; j < i+1000; j++){ //constructs the tree of factors of w5 of length at most 1000
  if(!(p->t[w5[j]])) p->t[w5[j]] = new_node();
  p = p->t[w5[j]];
 }
 rec(r, 0);
}
// gcc -O3 -o cc cc.c && ./cc