#include<stdio.h>
#include<string.h>
void affmot4(char mot[][5], int n)
{ int i;
  for(i=0;i<n;i++) printf("%s ",mot[i]);
  printf("\n");
}
void trimot4(char mot1[][5], char mot2[][5], int n)
{ int tete[26], liste, suite[n], i, j, l;
  liste=n-1;
  for(i=n;i--;) suite[i]=i-1;
  for(l=26;l--;) tete[l]=-1;
  for(j=4;j--;)
  { while(liste>=0)
    { i=liste, liste=suite[i];
      l=mot1[i][j]-'a';
      suite[i]=tete[l], tete[l]=i;
    }
    for(l=26;l--;) while(tete[l]>=0)
    { i=tete[l], tete[l]=suite[i];
      suite[i]=liste, liste=i;
    }
  }
  for(i=0;liste>=0;liste=suite[liste]) strcpy(mot2[i++],mot1[liste]);
}
void afft(int t[], int n)
{ int i;
  for(i=0;i<n;i++) printf("%u ",t[i]);
  printf("\n");
}
void trit(int t1[], int t2[], int n)
{ int tete[256], liste, suite[n], i, j, l;
  liste=n-1;
  for(i=n;i--;) suite[i]=i-1;
  for(l=256;l--;) tete[l]=-1;
  for(j=0;j<4;j++)
  { while(liste>=0)
    { i=liste, liste=suite[i];
      l=(t1[i]>>(j<<3))&255;
      suite[i]=tete[l], tete[l]=i;
    }
    for(l=256;l--;) while(tete[l]>=0)
    { i=tete[l], tete[l]=suite[i];
      suite[i]=liste, liste=i;
    }
  }
  for(i=0;liste>=0;liste=suite[liste]) t2[i++]=t1[liste];
}
int main()
{ int n=16, t1[n], t2[n], i, x=123456;
  char mot1[][5]={"truc","broc","bebe","bobo",
                  "troc","choc","baba","blog",
                  "turc","grec","banc","cric",
                  "talc","croc","stuc","clic"}, mot2[n][5];
  affmot4(mot1,n);
  trimot4(mot1,mot2,n);
  affmot4(mot2,n);
  for(i=n;i--;) t1[i]=x=12341*x+1;
  afft(t1,n);
  trit(t1,t2,n);
  afft(t2,n);
  return 0;
}