#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define Pi 3.141592653589
#define TOL .000001
#include "plist.c"

typedef struct
{ word w;            // Stores the word
  int mod2;          //
  matrix m; 
  double interval[2];
} right_word;

void right_word_destroy(w)
     right_word *w;
{
  word_destroy(&(w->w));
}

void right_word_copy(w,new)
     right_word *w,*new;
{
  word_copy(&(w->w),&(new->w));
  new->mod2=w->mod2;
  new->m.m[0][0]=w->m.m[0][0];
  new->m.m[0][1]=w->m.m[0][1];
  new->m.m[0][2]=w->m.m[0][2];
  new->m.m[1][0]=w->m.m[1][0];
  new->m.m[1][1]=w->m.m[1][1];
  new->m.m[1][2]=w->m.m[1][2];
  new->interval[0]=w->interval[0];
  new->interval[1]=w->interval[1];  
}
     

void right_word_empty(w)
     right_word *w;
{
  w->w.first=w->w.last=NULL;
  w->w.l=0;
  w->mod2=1;
  w->m.m[0][0]=1; w->m.m[0][1]=0; w->m.m[0][2]=0;
  w->m.m[1][0]=0; w->m.m[1][1]=1; w->m.m[1][2]=0;
  w->interval[0]=0;
  w->interval[1]=1;
}

void right_word_addLetter_r(w,i,r)
     right_word *w;
     int i;
     reflection *r;
{
  if (w->w.last!=NULL){   // theres is at least one letter
    w->w.last->next=(Pletter) malloc (sizeof(struct pletter));
    //pword_alloc++;
    w->w.last->next->l=i;
    w->w.last->next->next=NULL;
    w->w.last->next->prev=w->w.last;
    w->w.last=w->w.last->next;
  } else { // the first letter
    w->w.last=(Pletter) malloc (sizeof(struct pletter));
    //pword_alloc++;
    w->w.last->l=i;
    w->w.first=w->w.last;
    w->w.last->next=NULL;
    w->w.last->prev=NULL;
  }
  w->mod2*=-1;
  w->w.l++;
  timesEquals(&(w->m), &(r->m[i])); 
}

// a word_link is a pointer to the following structure
typedef struct tri_word_link_struct
{ word w1, w2, w3;
  int i1,i2,i3;
  struct tri_word_link_struct *next;
}  
*tri_word_link;

//Destroys the word link and all next word_links as well
void tri_word_link_destroy(wl)
      tri_word_link wl;
{
  tri_word_link i,j;
  i=wl;
  while (i!=NULL){
    j=i->next;
    word_destroy(&(i->w1));
    word_destroy(&(i->w2));
    word_destroy(&(i->w3));
    free(i);
    i=j;
  }
}    

// inserts a word into the word_link
// word is inserted in word length order
// then by lexigraphical order
// The original word will be destroyed
// No word will be inserted if there is a duplicate already in the list
// integers indicate type of word:
// positive: stable, negative unstable
tri_word_link tri_word_insert(wl,w1,i1,w2,i2,w3,i3)
     tri_word_link wl;
     word *w1,*w2,*w3;
     int i1,i2,i3;
{
  tri_word_link i,j;
  int temp;

  if (wl==NULL){
    // This is the first word

    // create a word_link
    wl=(tri_word_link) malloc (sizeof(struct tri_word_link_struct));
    wl->i1=i1;
    wl->i2=i2;
    wl->i3=i3;
    wl->next=NULL;
    word_empty(&(wl->w1));
    word_empty(&(wl->w2));
    word_empty(&(wl->w3));
        
    //word_link_create(wl);
    wl->w1.first=w1->first;
    wl->w1.last=w1->last;
    wl->w1.l=w1->l;
    wl->w2.first=w2->first;
    wl->w2.last=w2->last;
    wl->w2.l=w2->l;
    wl->w3.first=w3->first;
    wl->w3.last=w3->last;
    wl->w3.l=w3->l;

    w1->first=w1->last=NULL;
    w1->l=0;
    w2->first=w2->last=NULL;
    w2->l=0;
    w3->first=w3->last=NULL;
    w3->l=0;
    return wl;
  }
  if ((temp=word_compare(w1,&(wl->w1)))==0){
    // w equals the first word
    // destroy w and return
    word_destroy(w1);
    word_destroy(w2);
    word_destroy(w3);
    return wl;
  }
  if (temp==1){
    // w should be the first word
    i=wl;
    
    // create a word_link   
    wl=(tri_word_link) malloc (sizeof(struct tri_word_link_struct));
    wl->i1=i1;
    wl->i2=i2;
    wl->i3=i3;
    word_empty(&(wl->w1));
    word_empty(&(wl->w2));
    word_empty(&(wl->w3));
    
    wl->w1.first=w1->first;
    wl->w1.last=w1->last;
    wl->w1.l=w1->l;
    wl->w2.first=w2->first;
    wl->w2.last=w2->last;
    wl->w2.l=w2->l;
    wl->w3.first=w3->first;
    wl->w3.last=w3->last;
    wl->w3.l=w3->l;
    wl->next=i;
    
    w1->first=w1->last=NULL;
    w1->l=0;
    w2->first=w2->last=NULL;
    w2->l=0;
    w3->first=w3->last=NULL;
    w3->l=0;
    return wl;
  }
  i=wl;
  j=i->next;
  while ((j!=NULL)&&((temp=word_compare(w1,&(j->w1)))==-1)){
    i=j;
    j=i->next;
  }
  if (temp==0) {
    // words w and j->w are equal
    word_destroy(w1);
    word_destroy(w2);
    word_destroy(w3);
    return wl;
  }

  // create a word_link
  i->next=(tri_word_link) malloc (sizeof(struct tri_word_link_struct));
  i->next->i1=i1;
  i->next->i2=i2;
  i->next->i3=i3;
  word_empty(&(i->next->w1));
  word_empty(&(i->next->w2));
  word_empty(&(i->next->w3));
  
  i->next->w1.first=w1->first;
  i->next->w1.last=w1->last;
  i->next->w1.l=w1->l;
  i->next->w2.first=w2->first;
  i->next->w2.last=w2->last;
  i->next->w2.l=w2->l;
  i->next->w3.first=w3->first;
  i->next->w3.last=w3->last;
  i->next->w3.l=w3->l;
  i->next->next=j;

  w1->first=w1->last=NULL;
  w1->l=0;
  w2->first=w2->last=NULL;
  w2->l=0;
  w3->first=w3->last=NULL;
  w3->l=0;
  return wl;
}

void tri_word_link_print_file(file, wl)
    FILE *file; 
    tri_word_link wl;
{
  tri_word_link i;
  i=wl;
  while (i!=NULL){
    word_print_file(file,&(i->w1));
    fprintf(file,"%d\n",i->i1);
    word_print_file(file,&(i->w2));
    fprintf(file,"%d\n",i->i2);
    word_print_file(file,&(i->w3));
    fprintf(file,"%d\n",i->i3);
    i=i->next;
  }
}


int main(){
  double ang,theta;
  pcomplex z;
  int DEPTH;
  tri_word_link SUCCEED;
  triangle T;
  right_word *TRY, *w;
  word new1,new2,new3;
  int TRY_l,i,stab2,stab3;
  reflection r;
  Pletter l;

  SUCCEED=NULL;


  fscanf(stdin,"%lf",&ang);     // an angle of our triangle
  fscanf(stdin,"%d",&DEPTH);    // the depth to search to
  ang=ang*Pi/2;
  DEPTH=DEPTH/2;

  TRY=(right_word *)malloc(DEPTH * sizeof(right_word));
  T.z[0].x=-cos(ang);
  T.z[0].y=0;
  T.z[1].x=0;
  T.z[1].y=-sin(ang);
  T.z[2].x=T.z[2].y=0;

  reflect_from_triangle(T,&r); // stores the matrices of reflections  
  
  TRY_l=1;
  right_word_empty(&TRY[0]);
  right_word_addLetter_r(&TRY[0],0,&r);
  right_word_addLetter_r(&TRY[0],1,&r);
  right_word_addLetter_r(&TRY[0],2,&r);
  TRY[0].interval[0]=0;
  TRY[0].interval[1]=Pi/2;
  while (TRY_l>0){
    w=&(TRY[TRY_l-1]);
    //word_print_file(stderr,&(w->w));
    if (w->w.l>DEPTH) {
      right_word_destroy(w);
      TRY_l--;
    } else {
      z=eucTimes(&(w->m),T.z[w->w.last->l]);
      //fprintf(stderr,"z=(%lf, %lf)\n", z.x,z.y);
      theta=atan2(z.y,z.x);
      //fprintf(stderr,"Interval:[%lf, %lf]; theta=%lf\n",
      //	      w->interval[0], w->interval[1], theta);      
      if (theta<=w->interval[0]+TOL){
	if (w->mod2==1){ // even # of letters
	  right_word_addLetter_r(w,(w->w.last->l+2)%3,&r);
	} else {
	  right_word_addLetter_r(w,(w->w.last->l+1)%3,&r);
	}
      } else if (theta>=w->interval[1]-TOL){
	if (w->mod2==1){ // even # of letters
	  right_word_addLetter_r(w,(w->w.last->l+1)%3,&r);
	} else {
	  right_word_addLetter_r(w,(w->w.last->l+2)%3,&r);
	}
      } else { // it lies in the interval
	if ((w->w.last->l==2)&&(word_balance(&(w->w))==0)){
	  right_word_destroy(w);
	  TRY_l--;
	} else {
	  if (w->w.last->l==2) {
	    // We have a winner
	    word_copy(&(w->w),&new1);
	    if ((new1.l%2)==0){
	      //even # of letters
	      word_addLetter(&new1,0);
	      word_addLetter(&new1,1);
	    } else {
	      //odd # of letters
	      word_addLetter(&new1,1);
	      word_addLetter(&new1,0);
	    }
	    l=new1.last->prev->prev;
	    for (i=new1.l-4; i>0; i--){
	      word_addLetter(&new1,l->l);
	      l=l->prev;
	    }  
	    if (!word_palindrome(&new1)){
	      //fprintf(stderr,"psearch: not a palindrome.\n");
	      word_simplify(&new1);
	    }
	    word_empty(&new2);
	    l=new1.first;
	    i=0;
	    while (l!=NULL){
	      switch (l->l){
	      case 0:
		i=1-i;
		break;
	      case 1:
		word_addLetter(&new2,2);
		break;
	      case 2:
		word_addLetter(&new2,i);
		break;
	      }
	      l=l->next;
	    }
	    if (!word_palindrome(&new2)){
	      //fprintf(stderr,"psearch: not a palindrome.\n");
	      word_simplify(&new2);
	    }
	    if (word_balance(&new2)==0) 
	      stab2=1;
	    else 
	      stab2=-1;
	    word_empty(&new3);
	    l=new1.first;
	    i=0;
	    while (l!=NULL){
	      switch (l->l){
	      case 0:
		word_addLetter(&new3,2);
		break;
	      case 1:
		i=1-i;
		break;
	      case 2:
		word_addLetter(&new3,i);
		break;
	      }
	      l=l->next;
	    }
	    if (!word_palindrome(&new3)){
	      //fprintf(stderr,"psearch: not a palindrome.\n");
	      word_simplify(&new3);
	    }
	    if (word_balance(&new3)==0) 
	      stab3=1;
	    else 
	      stab3=-1;
	    SUCCEED=tri_word_insert(SUCCEED,&new1,-1,&new3,stab3,&new2,stab2);
	  }
	
	  right_word_copy(w,&(TRY[TRY_l]));
	  if (w->w.l%2==0){
	    right_word_addLetter_r(w,(w->w.last->l+1)%3,&r);
	    right_word_addLetter_r(&(TRY[TRY_l]),(TRY[TRY_l].w.last->l+2)%3,&r);
	  } else {
	    right_word_addLetter_r(w,(w->w.last->l+2)%3,&r);
	    right_word_addLetter_r(&(TRY[TRY_l]),(TRY[TRY_l].w.last->l+1)%3,&r);
	  }
	  w->interval[1]=theta;
	  TRY[TRY_l].interval[0]=theta;
	  TRY_l++;
	}
      }
    }
  }

  tri_word_link_print_file(stdout, SUCCEED);
  tri_word_link_destroy(SUCCEED);

  return 0;
}