#include<stdio.h>
int w[20],n,N=1,q,b[20], f[20],size_f,M[10][10],N;
 
type()
{ int i;
printf("%d\t ",N++);
for(i=1;i<=n;i++) printf("%d ",w[i]);
printf(" \n");
/* if(N%20==0) getchar();*/
}
 
void make_border()
{ int i=0,j;
  b[0]=-1;
  for (j=1;j<=size_f-1;j++)
  { b[j]=i;
    while (i>=0 && f[j+1]!=f[i+1])
    i=b[i];
    i=i+1;
  }
  b[size_f]=i;
}
 
void make_array()
{ int i,j;
  for(j=0;j<=q-1;j++)
  for(i=0;i<=size_f-1;i++)
  if(f[i+1]==j) M[i][j]=i+1;	 
  else { if (i>0) M[i][j]=M[b[i]][j];
         else M[i][j]=0;
       }
}
 
GenAvoid(int k, int dir, int i)
{ int h,j,m;
  if(k==n+1) type();
  else {  if(dir==0) for (j=0;j<=q-1 ;j++)
          {  h=M[i][j];
 	     if(h!=size_f)
             {  w[k]=j; m=(dir+j)%2;               	  
                if(q%2==1 && j!=0) m=(m+1)%2;	          
                GenAvoid(k+1,m, h );
	     }
          }	      	 
         else for (j=q-1;j>=0;j--) 
          {  h=M[i][j];
             if(h!=size_f)	 	        
             {  w[k]=j; m=(dir+j)%2;
 	 	if(q%2==1 && j!=0) m=(m+1)%2;      
 	        GenAvoid(k+1,m, h );
	     }
          }	       
 
       }      
}
 
main()
{ int i;
  printf("give n:"); scanf("%d",&n);
  printf("give the arity:");scanf("%d",&q);
  printf("give the length of the forbidden factor f:");scanf("%d",&size_f);
  printf("give the forbidden factor f:\n");
  for (i=1;i<=size_f;i++)
   {  printf("f[%d]=",i); scanf("%d",&f[i]);
   }
  make_border();
  make_array();
  GenAvoid(1,0,0);
}