/*  POTM ENTRY:  QuackTheDuck */
/*  Wolfram Hinderer (Eulfe)  */
/*  Your email:  bords@my-dejanews.com */
/*  compile instructions: cc QuackTheDuck.c    */

#include <stdio.h>
#include <string.h>

#include <sys/times.h>

#define TRUE 1 
#define FALSE 0

#define MAXGA 6                         
/* Maximal number of guesses that are collected before a guess is made.
   Only used in specialmode, i.e. after a guess with wordlen-1 hits. */
#define MAXWLEN 9  
/* maximal lenght of word */
#define MAXGUESSES 101
/* Maximal number of guesses that are allowed. It's funny that Fred did not
  make this 100, but 101. I had planned to submit another entry using 101 
  guesses for every word, but I did not have the time to do it. */

FILE *f;
/* Used for storing data between runs of the program. Stores the rank list
   afer the first run, which decompresses it. */

int wordlen;

char rank[MAXWLEN-2][26][26][27]; 
/* rank[pos][c1][c2][] stores the rank list of characters on position pos+2,
   given that on positions pos and pos+1 there are the character c1 and c2,
   respectively. */
char rank1[26];  /* rank list of the first letters of words */
char rank2[26][27]; 
/* rank list of the second letters of words, given the first letter */

char arank[MAXWLEN-2][26][26][27];  
char arank1[26];
char arank2[26][27];
/* the rank lists are saved in arank, arank1, arank2. rank, rank1 and rank2
   are filled up from these. */

int guesses;                   /* number of guesses already made */
char s[MAXGUESSES][MAXWLEN];   /* these guesses */
/* 0..25 are used for storing of characters. Exception: finalguess */
char h[MAXGUESSES],m[MAXGUESSES],nh[MAXGUESSES],nm[MAXGUESSES];
/* Number of hits, misses, non-hits, non-misses of the guesses. Should probably be integers or shorts. */
char h1[MAXGUESSES],nh1[MAXGUESSES],nm1[MAXGUESSES];
/* Number of hits, non-hits, non-misses if the word in the array guess was the
   hidden word. Builds up as guess builds up. */
char charanz[MAXGUESSES][26];
/* charanz[g][c] is the number of letters c in guess number g */
int charinguess[26]; /* Number of character in (new) guess */
char guess[MAXWLEN],finalguess[MAXWLEN+1],guessarr[MAXGA][MAXWLEN];
/* new guess (building up), the guess that is written,
   array of possible guesses (in specialmode) */
int anzpossguesses;    /* Number of possible guesses (in specialmode) */
int specialmode;       /* TRUE iff a guess with wordlen-1 hits has been made. */
char specialword[MAXWLEN];  /* the guess with wordeln-1 hits */

int bestsum;           
/* When no possible guess is found in 10 seconds, I guess the following word:
   whenever a word is found, that is possible except for that it has not enough
   non-misses for one of the previous guesses, the "number of non-misses" minus
   the "number of non-misses if this word was the hidden word" is summed 
   over all previous guesses. A word minimizing this sum is the output. */
   
int maxdepth;
/* only letters with a rank not exceeding maxdepth are used */

char relaxed;
/* If I can't find a possbile guess, then I relax the conditions, 
   i.e. the rank lists are filled up with the missing letters. */


void relax()   
/* Fills up ranklists with missing letters.
   Called when no possible guess can be found.
   For example, if the hidden word was QQQQQQQ, the rank lists for "QQ" would
   be empty, and earlier or later the program would find out, that there is
   no guess possible. The ranklists then are filled up, and every combination
   will appear somewhere, and is thus possible. */
{ 
  int i,j,k,l,m; 
  char d[26],d1[26];
  for (i=0;i<26;i++) d1[arank1[i]] = i;
  /* d1 stores which rank each letter has in the rank list for 
     the first letter */
  for (i=0;i<26;i++) {
      memcpy(d,arank1,26);
      k=0;
      for (j=0;j<26;j++) 
          if (arank2[i][j]>=0) 
             d[d1[arank2[i][j]]]=-1;
          else{
             for (;d[k]<0;k++);
             arank2[i][j] = d[k++];
          }
  }
  for (i=0; i<wordlen-2; i++)
    for (j=0; j<=25;j++)
        for (k=0; k<=25;k++) {
            memcpy(d,arank1,26);
            m=0;
            for (l=0;l<26;l++)
                if (arank[i][j][k][l]>=0)
                   d[d1[arank[i][j][k][l]]]=-1;
                else{
                   for (;d[m]<0;m++);
                   arank[i][j][k][l] = d[m++];
                }
        }
   /* The missing letters are added to the rank lists */
   maxdepth=1;    /* Start it all over */
   relaxed=TRUE;  /* Now we are in relaxed mode */
}




void saveandexit()
/* I finally found a guess. Save state in temporary file, print guess, exit */
{ 
  if (specialmode)  
/* If I have already found a word which right except for one letter, 
   I do something special */
  { 
    int i,j,anzdca,aapg=anzpossguesses;
    char dca[MAXGA*2],notnew[MAXGA*2],c,nnpos[MAXGA];
    for (i=0;i<anzpossguesses;i++)
      for (j=0;j<wordlen;j++)
          if (guessarr[i][j] != specialword[j])
             {dca[i] = dca[anzpossguesses+i-1]=guessarr[i][j]; nnpos[i]=j;}
    /* The collection of possible guesses is compared to specialword, i.e. the
       guess which was almost right. The different letter and its location
       are stored. */
    for (i=1;i<anzpossguesses;i++)
        for (j=0; (j < i) && (i<anzpossguesses);)
            if (dca[i] == dca[j]) 
               {dca[i] = dca[anzpossguesses-1];nnpos[i]=nnpos[--anzpossguesses];}
            else 
               j++;
    /* Only different letters are interesting in special mode */               
    anzdca = 0; 
    /* The number of letters that are possible for the new guess, but 
       appear already in specialword. The corresponding guesses will now be
       moved to the start of the array. */
    for (i=0;i<anzpossguesses;i++){
       notnew[i] = FALSE;
       for (j=0;j<wordlen;j++)
           if (dca[i] == specialword[j])
              notnew[i] = TRUE;
       if (notnew[i]){
          notnew[i] = notnew[anzdca];
          notnew[anzdca] = TRUE;
          c = dca[anzdca];
          dca[anzdca] = dca[i];
          dca[i] = c;
          nnpos[anzdca] = nnpos[i];
          anzdca++;
          }
     }
     
     if ((anzpossguesses>=4) || ((anzpossguesses==3) && (aapg>4)))
     /* It only makes sense to use special output if there are at least 4 
        different (new) letters in the possible guesses. Or if there are 3,
        but before uniquifying them there were more than 4. */
     {
        finalguess[0] = dca[anzdca]+'A';
        for (i=1; i<wordlen; i++)
            if (i<=2) finalguess[i] = dca[anzdca+1]+'A';
            else if (i<=5) finalguess[i] = dca[anzdca+2]+'A';
            else  finalguess[i] = dca[anzdca+3]+'A';
        /* Use one letter one, another letter twice, another letter thrice, 
           and fill the word up with another letter. */
        for (i=0; i < anzdca; i++){
          finalguess[wordlen-1] = finalguess[nnpos[i]];
          finalguess[nnpos[i]] = dca[i]+'A';
        }
        /* Guessing letters that are already in specialword does not 
           give information unless they are placed in their possible
           location. */
    }
    else if ((aapg!=0) || (finalguess[i]==-1))  
        /* This should be (finalguess[0]==-1), I think. Another Error! 
           But I think it was meaningless anyway. */
        /* If there have been 1 to 3 possible guesses, use the first of them.*/
         for (i=0; i<wordlen; i++) finalguess[i] = guessarr[0][i]+'A';
         
         
         
    if ((aapg==0) && (relaxed) && (finalguess[i]==-1))
    /* If no word was found, and we are in relaxed mode, and some other 
       funny condition is fulfilled (no word was almost right), then 
       something with high ranks is printed. Note that this can only happen
       when time is almost over: in relaxed mode every combination on letters
       will be found, if there is enough time. */
    {
      guess[0]=arank1[guesses];
      guess[1]=arank2[guess[0]][guesses];
      for (i=2;i<wordlen;i++) guess[i]=arank[i-2][guess[i-2]][guess[i-1]][guesses];
      for (i=0; i<wordlen; i++) finalguess[i] = guess[i]+'A';
    }  
         
    
    if ((aapg==0) && (!relaxed)) relax();
    /* No possible word and not yet relaxed: relax! Can happen only when time
       is over. finalguess has already been determined by checktime() */
          
    finalguess[wordlen]=0;
  }
  
  printf("%s",finalguess);
  
  f = fopen("TEMP.QuackTheDuck1","w");  /* filename proposed by Fred */
  fwrite(&wordlen,sizeof(wordlen),1,f);
  fwrite(&guesses,sizeof(guesses),1,f);
  fwrite(arank1,26,1,f);
  fwrite(arank2,26*27,1,f);
  fwrite(arank,(MAXWLEN-2)*26*26*27,1,f);
  fwrite(&maxdepth,sizeof(maxdepth),1,f);
  fwrite(s,MAXGUESSES*MAXWLEN,1,f);
  fwrite(h,MAXGUESSES,1,f);
  fwrite(m,MAXGUESSES,1,f);
  fwrite(nh,MAXGUESSES,1,f);
  fwrite(nm,MAXGUESSES,1,f);
  fwrite(charanz,MAXGUESSES*26,1,f);
  fwrite(&specialmode,4,1,f);
  fwrite(specialword,wordlen,1,f);
  fwrite(&relaxed,sizeof(relaxed),1,f);
  close(f);
  /* Everything I might need again is saved. */

  exit(0);
} 
 
  


void checktime()
/* Is there enough time left to look for possible guesses? */
{
static struct tms TMS;
times(&TMS);
if (TMS.tms_stime + TMS.tms_utime > 950)  /* 9.5 seconds over, time to go! */
{
   int i,j=0;
   if (anzpossguesses==0) 
   if (finalguess[0]==-1)
   /* time is over, but no guess found */
   {  
      for (j=0; j<maxdepth; j++)
          if (rank1[j]>=0) guess[0]=rank1[j];
      guess[wordlen-1] = guess[0];
      for (j=0; j<maxdepth; j++)
          if (rank2[guess[0]][j]>=0) guess[1]=rank2[guess[0]][j];
      for (i=2; i<wordlen; i++)
          for (j=0; j<maxdepth; j++)
              if(rank[i-2][guess[i-2]][guess[i-1]][j]>=0) {guess[i] = rank[i-2][guess[i-2]][guess[i-1]][j];}
      for (j=0; j<wordlen; j++) finalguess[j]=guess[j]+'A'; 
      /* finalguess is filled with high ranked letters */
      finalguess[wordlen]=0;
      if (relaxed) for (j=0;j<wordlen;j++) {finalguess[j]+=j+guesses*wordlen;while ((finalguess[j]>'Z') || (finalguess[j]<'A')) finalguess[j]-=26;}
      /* seems to be useful, as relaxed rank lists look to similar: 
         I don't want to guess QQQQQQQQQ over and over again. */
/*      if (maxdepth<25) maxdepth++; */ 
/* Not sure if this is useful, but seemed no longer necessary */
   }
   saveandexit();
}
}


void doguess()
/* Hey, I found a possible guess! What should I do with it? */
{
  int i,j;
  char newguess=TRUE;
  /*           ^^^^^ this was missing in the submitted version */
  
  
  /* I played around a little with restrictions on the first guesses:
     no repeated letters and so on. Not sure if it's useful. */
  if ((guesses<1) && (wordlen<=9))
  {
    for (i=0; i<26; i++)
        if (charinguess[i]>1) return;
    if (charinguess[guess[wordlen-1]]>0) return;
    if (charinguess[25]>0) return;
  }
  else if ((guesses>0) && (guesses<3) && (h[guesses-1]<2) && (wordlen<=9))
  {
    for (i=0; i<26; i++)
        if (charinguess[i]>h[guesses-1]+guesses/2+1) return;
    if (charinguess[guess[wordlen-1]]>h[guesses-1]+guesses/2) return;
  }


  
  for (i=0; i<wordlen; i++) finalguess[i] = guess[i]+'A';
  finalguess[wordlen] = 0;
  /* the final guess is determined... */  
  if (!specialmode) saveandexit();
  /* ... unless I am in specialmode! */
  for (j=0;j<anzpossguesses;j++)  
  /* I have to check if this guess is already in my list: when maxdepth is
     increased, all possible guesses in the list will be found again. */
      {
      newguess=FALSE;
      for (i=0; i < wordlen; i++) 
          if (guess[i]!=guessarr[j][i]) newguess=TRUE;
      if (!newguess) break;
      /* If one letter differs, then the words are different */
      }
  /* guess has been compared to every word in the list. If it's not new,
     everything is ok, nothing has to be done. But if it is not new, then
     the value of newguess is only defined if the list is not empty. So if
     the list is empty, it might stay empty... something like that was what
     happened with my entry. */
  if (newguess) {memcpy(guessarr[anzpossguesses++],guess,wordlen);}
  if (anzpossguesses >= MAXGA) saveandexit();
  /* more than 6 guesses are not needed */
}





void generateguess2(int n)
/* guess n-th letter (n>2) */
{
  int j,k;
  char r,possible;
  char  ah1[MAXGUESSES],anh1[MAXGUESSES],anm1[MAXGUESSES]; 
  /* store old (german: alt) arrays of information */
  char *ch;
  
  ch = rank[n-2][guess[n-2]][guess[n-1]];
  /* Here starts the rank list */
  
  if (*ch<0) return; 
  /* If no combination is possible: return immediately.
     (This might be possible because there are short words with funny endings
      that are not part of a triple in longer words.)
     I'm not sure if it's worth it. Saves time for copying the arrays. */
  if ((n==3) /*|| (n==wordlen-2)*/) checktime();
  memcpy(ah1,h1,guesses); 
  memcpy(anm1,nm1,guesses);
  memcpy(anh1,nh1,guesses);

  while (0<= (r =*ch) )
  {
    possible = TRUE;
    for (j=0; j < guesses; j++) 
    {
       if (s[j][n] == r) { if ((++h1[j]) > h[j]) {possible = FALSE;break;}}
       /* If current letter (in rank list) would be a hit, increase number of
          hits of current guess for previous guess no. j, and compare it to 
          the number of hits actually in guess no. j. */
          else           { if ((++nh1[j]) > nh[j]) {possible = FALSE;break;}}
       /* Do the some with non-hits... */   
       if (charinguess[r]==0) { if ((nm1[j]+=charanz[j][r])>nm[j]) {possible = FALSE;break;}}
       /* ...and with non-misses */
    }
    if (possible) 
    { int sum=0;
      guess[n] = r;
      /* So, the n-th letter of the new guess becomes the letter in 
         the rank list */
      if (n==wordlen-1){
         /* Hey, the new guess is completed!*/
         for (k=0; k < guesses; k++) sum+=nm[k]-nm1[k];
         /* ...unless there are not enough non-misses */
         if (sum==0)
            doguess();  /* Number of non-misses is ok */
         else if (sum<bestsum) 
            /* The number of non-misses in not ok, but the difference is lower
               than ever before. If no possible word is found, this will be the
               guess. */
               {for (k=0;k<wordlen;k++) finalguess[k]=guess[k]+'A'; 
                bestsum=sum;}
      } 
      else { 
      /* If there are more letters to generate, increase the count of 
         characters r in the word, and generate the next letter! */
         charinguess[r]++;
         generateguess2(n+1);
         charinguess[r]--;
      }
    }
    memcpy(h1,ah1,guesses); 
    memcpy(nm1,anm1,guesses); 
    memcpy(nh1,anh1,guesses);
    ch++;
    /* For the next character, restore the values of the arrays with the 
       counters. */
  }
}


void generateguess1()
/* Generate the second letter of a new guess. Similar to generateguess2. */
{
  int j;
  char r,possible;
  char  ah1[MAXGUESSES],anh1[MAXGUESSES],anm1[MAXGUESSES];
  char *ch;
  
  memcpy(ah1,h1,guesses); 
  memcpy(anm1,nm1,guesses);
  memcpy(anh1,nh1,guesses);
  
  ch = rank2[guess[0]];
  
  while (0<= (r=*ch))
  {
    possible=TRUE;
    for (j=0; j < guesses; j++) 
    {
       if (s[j][1] == r) { if ((++h1[j])>h[j]) possible = FALSE;}
          else           { if ((++nh1[j])>nh[j]) possible = FALSE;}
       if (charinguess[r]==0) { if ((nm1[j]+=charanz[j][r])>nm[j]) possible = FALSE;}
    }
    if (possible) 
    {
      guess[1] = r;
      charinguess[r]++;
      generateguess2(2);
      charinguess[r]--;
    }   
    memcpy(h1,ah1,guesses); 
    memcpy(nm1,anm1,guesses); 
    memcpy(nh1,anh1,guesses);
    ch++;
    checktime();
  }
}



void generateguess()
/* Generate the first letter of a new guess. Similar to generateguess2
   and generateguess1, but simpler, and with a few initializations. */
{
  int i,j;
  char r,possible;
  
  for (i=0; i<=25; charinguess[i++]=0);
  for (i=0;i<wordlen; guess[i++]=-1);
  while  (maxdepth<=25)
  { 
    rank1[maxdepth] = arank1[maxdepth];
    for (i=0;i<26;i++) rank2[i][maxdepth] = arank2[i][maxdepth];
    for (i=0;i<wordlen-2;i++) for (j=0;j<26;j++) for (r=0;r<26;r++) rank[i][j][r][maxdepth] = arank[i][j][r][maxdepth];
    maxdepth++;
    /* The rank lists are filled with one more letter. */
    i=0;
    while (0<= (r=rank1[i++]))
    {
      possible = TRUE;
      for (j=0; j<guesses; j++)
      {
        if (s[j][0] == r) { h1[j]=1; nh1[j]=0; if (h1[j]>h[j]) possible = FALSE;}
        else              { h1[j]=0; nh1[j]=1; if (nh1[j]>nh[j]) possible=FALSE;}
        if ((nm1[j]=charanz[j][r]) > nm[j]) possible=FALSE;
      }
      if (possible)
      {
        guess[0] = r;
        charinguess[r]++;
        generateguess1();
        charinguess[r]--;
      }
     }
   }
}



void answerguess(char s2[], int h2, int m2)
/* The last guess, s2, had h2 hits and m2 misses. */
{
  int i;
  memcpy(s[guesses],s2,wordlen);
  h[guesses] = h2;
  nh[guesses] = wordlen-h2;
  /* hits and non-hits */
  for (i=0; i<=25; i++) charanz[guesses][i] = 0;
  for (i=0; i<wordlen; i++) charanz[guesses][s2[i]]++;
  /* The count of each character in the guess is computed. */
  m[guesses] = m2;
  nm[guesses] = wordlen-m2;
  /* misses and non-misses */
  guesses++;
  
  if (h2 == wordlen-1) {specialmode = TRUE; memcpy(specialword,s2,wordlen);}
  /* If all letters except for one are hits, turn on specialmode.
     This means, that not the first possible word is printed, but that
     several are collected, and a guess yielding (hopefully) more information
     is printed. (If there are less then 4 possible guesses, behaviour
     should not change.)
     
     I have to say it again: On Fred's machine, no guesses were collected,
     as a variable was not (or wrongly) initialized. This was a problem only
     for an empty list, but the list remained empty because of this bug...
     
     [The specialmode workes quite good, and for the word WITHOUT there
     were less than 4 possible guesses left, and the first word found was
     WITHOUT, so QuackTheDuck would have been better without specialmode
     in this special case (without the buggy specialmode, that is).]
     
     For Fred's twelve extra word, specialmode was a big help. */
}

  
void main()
{
  int i,hinp,minp,l,k,j,emptylines;
  char s1[20];
  unsigned char c,c1,c2,c3,c4,c5;
  unsigned long n;
  char datastr[] = ".vhG:QDrvA~QLa&mwJF<:g&r7Z)KuO:{O*~Tfcy4i.OQ> 7mRNn9aO$$^Xg4i-(.A)tjN8q-gr`4$S88{E+m!hkQ]IYF9x@)#j ʕ.GKz$N:[ݜH .xf1!zO8H;zLO*ι^:pNIK g,mTd:wQY3EŐOfqJi,<3q[RH!k(r>ZK1$`7r/2PlH-];^J7Qbė.~Eq(7b>o:|./[G)8rtFb{諒4^k@P$HZ`ٹRq;s$St4_(ެFx{H!eIj*~cnnC9[w@n@$:~薒i#E5gIH}r`4n0WeO:q]؇-;;W>aՐ~1O=a1zNCnw>`Nq<$obq4->TﴑĪqTb(,;9Y0mgLE n.Qx_NIBDm0c`(܃,D#vLVahB,m sa:Rr-JS7y$N|o؄rc}2}Ndoa`)Jj:hkcAIF`;{;hi`4(]΃}{+8q4DCN#U}xJՕ/Iq29s<fn/ފh*LƂh.-`!d;v{ :NIЖn;;pR~_),Z==)po&b+-$~taDNb7;r`b9BF2ք[fҐ8C[%hh77ND=}rq<x$c#Qnn:>VĈ9xX<:3isJ%xۆgY)F<$P=:5,8Ba{,>'xTsϕ(^2,t&:O/g{!CqO,;z``z`rPJn!?.l!fey>$PJ$cƷ+7[0gy̢Y9T@'/E`{Tm&+)W2l6{=E#4]U;'Ig;݆]#7Q眄ea,?:9E$ƓܬD9#X>k7d$$1f+ТYET5rQkmMfC,51HʄKĊ==G.8s5t vŅ'BxakA)>Obos![CC5D2]hۚhZa7M'5m_ENo-~EiO7J:N4AbfHw޴m>;FO2k⅗hEx1XFrpx1rIy0 'x!Inqk4f#׌b1BxjMۋVyU@1s<r5rd5޷&x$P˫tRkT`z.#t;KȾD#v`by(!OSK@-ŹnNd9nT=EbwT`2E23`'E*NNn9k8b2x`:pNKcQsCfF2u!dt7Xm-e=~ZEʿwNլ2wK?p<wJ_2WmF8aqȓCBs&9;Ԋyeȡ?zl]}gׅ'=x{5cNF!&=usHO$4`m3uz(PD]=Fq/R4r`4rxu`ph=dq-3Wp7ZK˘ Pty-O?2zJNda.Zmڄs-]8r+Ⱥb027>.ZO!lvaEyhragNnZm$:xg+83ѽ {J($t!a {w.2ʑwJ%l([F%~Ko3Nw+ھ+k;xKR9`C5Q4˘e8 9m!+6<[DdDbP56~P,22'w8ɂw<a:|8(9Trn1ud넟Fcr!mN4eТ+ιJ0|fƇ1kt9gRpY4BdG͹s7o P1^2Qpq'.ewɺr7`hVE=_|3k;n#1lC<sxu`P,-m64h@2r!dJӖ9&Qlh.=HFծ9fs蕙CfN9^s@x)~+`,Pw]7LNq&`g5.@LbiQ8n,g~,? _oE(OZ;q(k[8&#4cB8qnCe {@y;|3+;mNnB̭kǺNu`V;{Rqu4f0N|:~,j$PfRTm7xņ!ڷ7NN?4grqPbࡀ5;_;uN;|?/zvLʹN>#X.JO1`+gORۃ4m.$`~yhyNdJ-9ї7NڬDrz$yk8uV/e84kxC9N{Zb/u4Bs'w5˄,HOnQrdb?$`9`>;iNnlb=YxuL$LPPFq$./Ê5Lvlu^em04Oq-E@o[kmeCVqyfڈr-Z*2XJܒO8-ale'Itbzek&iZ;t`Ndq(gNiQp;U3[Gr<)rL;$RsR4go|7Cwm/r|4N> ;$ǊehNZ)ZE˴7QqsgOJo*.'9B4OqX;v?Jk4!jÅ9bg1`$~bnhm7'Ɛ,r`^<:Sq1o8;j:zvc/?)P:Q#l7Fsh¢{;RZIԄcTq0=Yl;~xȊy_FZ {?`͡_cB;bP;| {PSDv]AyHeE 45l-p,!d %ib;yq($;lNsC$HO)Zb˝*olxm]K=<$Fm79).s5XQ)ڨ%qXIN;ttkhFD7z|;vr`-=%V$vq#XnP$xIHڐ^әrZ?LqqʏP:r`i.O[r $PK8`󢣲^&O`!0D.sq͕ 82`bE9&~d&.dgm(]OdIhuaQ/rt -˜R2a;yq($Z$APs#zJ7gtjRkhq(4NzuV Ĺp.z(Pbz_taNnO$y;#H;rs̔ܢSG ,&ord`x>@1rKP4ilzCg*-P0icNjt@;lEC`J]59gQNHNeOrs@U`kbto-~E϶;vq(tNאLZeE={1'<4Bߋf=F6s4UxǒN`Frw: O*KZYĒLhHlBrb;KHQL-al`LI-bxqbvӷd!dkK'3hKN=G+:6P11;{膱e`RO/9e3<N_PD.3M7Rw;!zmQ}C<:cR7NRKR9m#/;G,8-Ӌx=`]1}WRGO#!d̈1śP~))tPD9ow>)G<1v:(Nd$`N`;QHquh&CWU!VNzIN;zQIH,gNE#aa;p$t7s? _3B0qO`;vgLrkj?;H7ZuVce8Hq$r`;i'd/(b'>V>]սo$sya&O,k[>ւyƷuHymB#N$q;| s̸`>ki$ld*xƿa4bNIj(Ҏ!lC`?}TL5nH#a|5! |Db-P=4F#Trl_ckm%$W1ty8E i̺0gq$?8,8 V@r?9(Qy9_g+?J}KO9_P-zNrlw]aĒ8O$É-R3367_9~a//BlYPxʊ$!ЂR>hV`ſRa]j(;iٽ`Kh3b_u[N{`Nk:$paގ`zιLPcظo[cq$9l3=?t*Pk;O*_*&CN+qlI>Rm!z~Ky,8v$$b0TFalȚ/c!a|qKrd_Č1O*sl?%cJNs?tshuvq:NIBO+s?8w˺%Phv$FZk8ƲIeĐwKrk=4<Q:f4`aZn zKOgYC3IZ.k[@័ogR7O*k?Urd(mEH;y`.&c𫘊xcr`4c&NxRs޷Ja&qj$LO*8ڡ/Y޾8j7sc!qvmH%$LpIЊxrط;lRyQ'#7Թ_!d?2㭰N xfB(b`x@(Nt>N84NI#=fxZ;|#^h@Pas50hm7hvx4r9&#踿e1{&6fNnOfYq/$qa1Nnrz0Ndnartu]q$@N7L/Њ(5(8OXR]&3r-śrNqJ82`h!*Ig)Ĝ`3n']eښlĐq7Z`frxDgVJdcN#>?Hȭ8s|_l,?DܕLb.;kox0.ʈSN`L})}g+@N:;,1`,WT_ŸeN;y;7H;jHc-e7߇<V#789O*t[<ox><CPb;h RC38N;v㉄L(3:^`o(C3Pf%_ fHO+f:fkO7ogP&j;q( ʮ88tPJs`NI8$wPtH$R;ve$y$a:.}ha_Pw*`bY~uO*r`nRNVkO]q<$_'μko]'`kt* KtNO*ET!DwQL`<L!%fш޺k<R;hcꉄt/%e/L7Z!s?E2QJq-&Ĺ]m;{#8NrA!ֈ#k'Ţ:fweȮ1#T,mKi ʭ@*$bkm]by3em;)lk͗cIh$gR;vuV`ِ$ҒI$r?h+4x7`7NBJQO*a@+.ec<=JD(xC+99xo3gQ9k_ȸwrd3t5J÷rdI4Ŏ&'PK;/L!dqg]#k:fHVRsKyP3r+mqO*8D;s@$WtEĉ_ZTcNdf1鸿4et7#w23>.oE8߷KP`Nd>sи4X;T!ЉK'@q;rJkn Z{!PO5-#T;vW_d;r#)@kEoKfT9kO)X @;hQSq4K)?o$^k7S>w(Qq4;pbfP`qO*q8ݭmFx7Uua@Nn;l Hxz3= s̖/$!9C&@Z}uO*H;prx8-UO&rԖ^@H>Дa:1rfkOkRq3t7QbRc؊W ;p_)$rd3<L% s`;K,,?3g;l/.sO_FZMLleC:tal!o).I^8vT_&IxꕵP4e.j(WA!dob&dfTrTS5:(J-b)uNu`IjDml!qms-23]CuP7HuVrPwqֺo`#8@Rl;'cㄗCM$a8HCDe)Ihy$_PLQr̄0O*aHkh/L#k=c&rg]Ϩ;΄D;z!ԉjqoq1g.XH2O*!ޭ?Q8N&t$[rdb}+O*sDo)+WC([ؐ5gqHºtRp;org#cb.R >~EIeɛo;yq($883Du)m$ٖ3e$P:~a!oe&^wOLQO!;v` E4xo4^,cr<;v;{q(Nz~7Zcxw9PK(7TO*8b@H;uq(@e.)7K{@cnd(4fq!VRe-or آmRq49;v!n4i`eysNfXE}7$3;;p@$VNdn.H.NCu]R9xtpIX(`#Kfhkabx1u[q{<D*@VߊU'SJRNJtO1m4$V8'=y/fnCQ$Urx&^ڹ [Cb>=w.Nm5C;:2`cqSnv:0 y1fZhNg~/a[K!d.`MO+$YO*Jc3eHꏡb4e#reT|nU t/F6ub{Bdl`u[u;hRQs?:YurtڷċY+O+rq8Nzx;CKtacܕwʢ~9ג`Z$g]uUi9VQV;g$WxPH;dr'uK8vZȆ#jO`ro|$Zqعssfq<?8EݒC`NR:^PRs+%uvbobn3ɗqKh^c!n)8v_/;|H)l'/I!.;vreqʃp#]q:aވC_h;v5am!􎀭8?H;|%shȹ4:*:)vIa׿8S-`frٌ|:T]78~O*+bflnCZ;yq(_ʊO5;uhO!ym/e+֭jO*_$z4NQnuN2+q{O,q8O+aުtSN9J<n.$IobBuul >){O,r(@돾Nbw4;a'inwUO rtgț^38p|:._¸8v0Ung&$]d;ocn.hkq+7zPrt;hDtq(9n {(3ZR;#蹾r`Ji%ta`򺛷u!dtrOPT_ :3LR9x8ΐmC>C)q::ĒPI@,FRtT#bw'g(L[EQ8k7Z)OrQnCwouY#7lRjGe۸%m[޺r,`B[5by=]:f`kh Dy1ηQ[!@&F`hq3`0z;uq(q:&cm!dbf01O*`2[Au7O*seQo.57;@$J1;r`$`QLccrfRn/fwu]ӈsG7Kx7;}RP0X:fT'tc17dq!dN$P!7rq;$PNL8b$yoax4٢$aq1l:p8R>:+1`7X$P:6!d3s$E/&NnQO*>f2rڽlbHيg.8k^$YKbq!ds:nbZR tcJpoNdPFq$[qh|FNdOm+@o-oCJg -xKNe,x!z|.o=;.O*TqelnUՏ4SukzL*9Ocf|Pso|b$H!dз0q]$ZrksLQz_lNn{)Rrp,)áuO@J;yoCev7oE-rt7@.2hxաu_O*#)uw$[|JEVRThK0KX(;2O*s#5#>dEG;$PR&#m#?rfw9&R;ve@>b! ;pq(; -oD#4o>ҬNg+Ò?7[$tD-WIO;~#^8vq(ap;zHK=@{/9=ra2ꬴ$8n.$)y.`= QL<-Rq;hO*tnhR&Jq׺QR:fJg+ěfRscCQhlM8l;}@k֊O*q$9pO*# (3yGNeDuP7L-΅c;v:P/H?oNds@RېU@BoK| _ȹ:T1&Dl@ޕO*oxO*!OgʺqD(LNd;v<fR$LO~Pv(۸S J4O괘Ca$$Y8Po.yJ;p@$lb7r;}89IZ!nsq#L-~!r`$}:!dPvCWzŊ墜IJqʺ`N#^;ysϮ54r-yD8wQa$q;z#ONdk B򛋹;valDx'!dO*%gQUt47ly.=XV*;JЄRJȎ2+O*!tW(U4r95O*`Nnse_k4GaYQ9Nq:r`Iisr%wrzq;yq(mK)q lbeCDbQP$`:$PbX=!dm.rd낪ϕ=Lz8.y5J7N.Rm/&iKu`NLr̸kg^4O6I;!`$Y;|g@wmBqufTFG(eŬRDq:rdoxs!3wrTA)r$} dTIB;D0krEO$tObGH;prwOY$U&:f[GrO*`Bb#/xLkҶb͈;0LOrϫmE;kQ5C;Z:^O*kbC]9;j!sqo^!dKgdR;nwC^'9$oˎ7`Q$Hc)ae7Z$VP8($NrO+o7`O,7ZO*憣LO#Lxeտ3Nh1*gp0EuSk͗2ҌQ!|r ʥ?>;r!{`L`dl(ʈgY9qBO,$VOsN0Nq8:f[GxO*qˉ.;{`o7NaފCNuaO*rL#SZZP!dJ48BҭEy:85Ԉ]$eȄJO#JJO*jEF;q($l;z;p!r$Ubք:.N4P?;2+bx;rxKm$rd;|;v`d nK.ex$!َO,t[>x7w-;(;hr`elxCN|>R|efg0bc(Aq:$`9&n;Nr`;|$P7M.?S)~O(7ZJ-ulNu``9ZH7NRi4_g9uN_ȹyr`zFWNxb= E rq1vf¹y;h&D?H;}kXw&ЈNk[!Nsy3OntDn1w=<K7|aII|ZsЏO*h8F8O~O*/֧$y4Om.;lkj`mq̼X&aBχ6n;8cN#Fl7RO*0!drDa7$PK$tPxjGo(΢wqʶ$V7:WNfQ$VO*9n.{g0!d7Zp$cn(OC:$VutNdu;{s@ۆ7R``o-oNktT$`akO*CZs4Fn@ؖL#]'4;;`# Ndv֍4B/`z<fJ+LfCrraX8q4/It!duV;h;hӏCMNn$r4NYuH7T`m;hqO*ʾN#juVrdAN4p=Iu]H;v4rP C)`$oxBr=QDs;|Jgԅ~QVuXSRYR!Jn_`aHrd,?(N5~BN۪ማ<P$Pk@.K7HtbOi.bhQ+Cs[0;~_O*K;h|`M:dq-!>`rt4#)QZ({d3O ȷJNdmHݛӘCRO*c ʊӷĽ$T1ɐNzPbO8>nkON:x܊~3W;|O*gL'IO*(js!dt/`aZy=O*q2 4Du=fTr;_[EO*`QL_q;Br&R`OQW4Q6,PţNTo+/Nd;Jm-Nڢ~;|Rķ>rdjqbbk!dbe:xH?r;|`v!dÅ[_fzryR:prdJ7MN)_fA;l8NO*xuSRO]>.b7K!d!d[*;{L~.b/=!d$VrdxK'C3Z#jn7N4ra#O*>:O*o:&>?h;($O(7Zpo|a=q:RlrdXfҶP(P9a;|#W`mPfqO*.<o}7Ŋ;4îRD;hQn.bB:|(Nq<:xiW;|!Ը6 (.*Rq:;yc,?lYRsKpCn&bAQHn3xK:L+.;m(r,F#0ZRb;n@%qO*۸Ijg'O5`N!q_-k'=$N`{4NIKNd-ΎO*;zO*raO,6[3܊'21q+7Zo6Ndqʽ:f$tQIZ$U7ZRO+4u7ҺdR00ko!ltNtkA8;{#^uh4AO+c22;Nrt,?O[L<;#+gOnPZHt`R^,T##;l/ngC]R4N!7$$sE$Ύy,=m`ðO*g[~q:C`?m4.;L 2+:;5n;<n0t7.gN6}b0ZtBȐn&fκrH$=P7Z7qOXoԌF_Q1NqIqd ʌp0:B-67:B,la֨MtKruVn{E4F`m`{#Fl-5#;o Ŭul;oao/IĖF4uka9;ow@ry甼Rj;vrތ~a.w/;:(KP;|F4F/-*lȌDc踻lY.`T#`ʈH:f[+hO<t;Rnlrk:9o,pXNCҺnbm#C3#9.<2Xŀ QV7ZG4/Lk׽u`;lHoTP.C^;r_-ѳ2 kJ|nݸqc󄗈IC`җ4rm-;3ecb$LN=;0O+h^buqʕp:B{*@4І.{Nd!«pA;Ns: 5kT5 hC@iT15mJr< hl,qO*KIZQ~xf;yoxbĹl<Hz7Ra7 ̌bO ;l:B@nvDbDyݷ8v ­CkH+_Ĉ9o.y_8B;QH;sҹt]#-a[y;tqʹsHwrͤI[hbw.;ruHq:(4Fɬ[Ы7Z;zO@q˕;rr_iQYdfx}L5nIPܗꫫ`-啌$@lࡅr z`c!x>;vPs @.+Oms[/bnca;9&QH5E7ʐZ XNf9&Kr8n;ڂ};`N˙#94QCGoQSŇ5kj=~Ll94sʡam5ǚQk1|0IZqQO*O4uɭ̽7oAj;{1Ŋ:B3#hwf7CO=`5k̷ӈ׈QJv56*9Gm;R4s;$`{*ik9fk$pwZǾK8 ʅr3I{ g5l=40:;㸮n;2:^Ki;y{Wa쯃^bw/گpl:BnR<MXge~:hi-y;z:BH˹l`=5Tg^F2e2;s9Cc;:KJȚݴ1W`s$i1ą[is0kq2r`鴮ep^È0e2[;7R5:9:C+:nT$KD򸍒8gJSqʺrz;85D%:BE[ӎьs :Cg@n_#07#Fr@zߊo+3X4QFX7Z4<|d3؊8w56n` kjwiعHdv4skԕ #k≛@Rdu[9`/Ծ(Z;hNdh;JNAI ̹CFs4;{K|zm_4Qn}pC;=ʗv ";
  /* That's the table with the statistics.
     I used my spell dictionary to create it.
     I compressed the rank lists by putting 3 characters in 2 bytes.
     I tried not to use special characters, as I tried to send it by plain mail.
  */
  c=getchar();
  ungetc(c,stdin);
  if ((c>='0') && (c<='9'))
    {
    scanf("%s",s1);
    }
  else
    {
    scanf("%s%d%d",s1,&hinp,&minp);
    }
  
    
  if (strlen(s1)==1)  
  /* New game! Initialize everything., */
  {
    wordlen = s1[0]-'0';

    f = fopen("TEMP.QuackTheDuck1","w");
    for (i=0; i < strlen(datastr); i++)
    {
      c4 = datastr[i];
      if(c4==10)c4=datastr[++i];
      c5 = datastr[++i];
      if(c5==10)c5=datastr[++i];
      
      if (c4==31) c4=34; 
      else if (c4==30) c4=92;
      if (c5==31)  c5=34; 
      else if (c5==30) c5=92;
      
      n = ((long)c4-(long)32)*(long)(256-32) + (long)c5-32;
      
      c3 = (char)(n / (long)(36*36));
      n = n % (36*36);
      c2 = (char)(n / (long)36);
      c1 = (char)(n % (long)36);
      if (c1>=26) c1 += '0'-26; else c1 += 'A';
      if (c2>=26) c2 += '0'-26; else c2 += 'A';
      if (c3>=26) c3 += '0'-26; else c3 += 'A';
      fprintf(f,"%c%c%c",c1,c2,c3);
    }
    
    fprintf(f,"0\n");
    fflush(f);
    close(f);
    
    f = fopen("TEMP.QuackTheDuck1","r");
    /* here only used for an intermediate stage */

    for (i=0;i<=25;arank1[i++]=-1);
    for (i=0;i<=25;i++)
        for(j=0;j<=26;arank2[i][j++]=-1);
    for (i=0; i<wordlen-2; i++)
        for (j=0;j<=25;j++)
            for (k=0; k<= 25;k++)
                for (l=0; l<= 26; arank[i][j][k][l++]=-1);   
    
    
    l= 0; 
    fscanf(f,"%c",&c);
    fscanf(f,"%c",&c);
    while ((c>='A') && (c<='Z'))
    {
      arank1[l++] = c-'A';
      fscanf(f,"%c",&c);
    }
    k=-1;
    i=j=0;
    while (j==0){
      if ((c>='0') && (c<='9')){
       emptylines = 0;
       while ((c>='0') && (c<='9')){
         emptylines = 10*emptylines+c-'0';
         fscanf(f,"%c",&c);}
       l = 0;
       k += emptylines+1;
       j += k/26;
       k %= 26;
       i += j/26;
       j %= 26;
      }
      else{
        arank2[k][l++] = c-'A';
        fscanf(f,"%c",&c);}
    }   
    j=0;
    while (i<wordlen-2){
     if ((c>='0') && (c<='9')){
        emptylines = 0;
        while ((c>='0') && (c<='9'))
       {
         emptylines = 10*emptylines+c-'0';
         fscanf(f,"%c",&c);
       }
       l = 0;
       k += emptylines+1;
       j += k/26;
       k %= 26;
       i += j/26;
       j %= 26;
     }
     else{
       arank[i][j][k][l++] = c-'A';
       fscanf(f,"%c",&c);
     }
    }
    close(f);
    maxdepth = guesses = 0;
    specialmode = FALSE;
    relaxed = FALSE;    
  }
  else  
  /* If we are continuing, read data saved in the temporary file */
  {
    f = fopen("TEMP.QuackTheDuck1","r");
    fread(&wordlen,4,1,f);
    fread(&guesses,4,1,f);
    fread(arank1,26,1,f);
    fread(arank2,26*27,1,f);
    fread(arank,(MAXWLEN-2)*26*26*27,1,f);
    fread(&maxdepth,sizeof(maxdepth),1,f);
    fread(s,MAXGUESSES*MAXWLEN,1,f);
    fread(h,MAXGUESSES,1,f);
    fread(m,MAXGUESSES,1,f);
    fread(nh,MAXGUESSES,1,f);
    fread(nm,MAXGUESSES,1,f);
    fread(charanz,MAXGUESSES*26,1,f); 
    fread(&specialmode,4,1,f);
    fread(specialword,wordlen,1,f);
    fread(&relaxed,sizeof(relaxed),1,f);
    close(f);
    for (i=0; i < wordlen; i++) s1[i] -= 'A';
    if (guesses<=3) maxdepth=0; else maxdepth--;
    /* As the first guesses are treated specially, reset maxdepth. */
    answerguess(s1,hinp,minp);
    /* create tables for the guess */
  }  

  memcpy(rank1,arank1,26);
  memcpy(rank2,arank2,26*27);
  memcpy(rank,arank,7*26*26*27);
  for (i=maxdepth+1;i<=25;rank1[i++]=-1);
  for (i=0;i<=25;i++)
   for(j=maxdepth+1;j<=25;rank2[i][j++]=-1);
  for (i=0; i<wordlen-2; i++)
   for (j=0;j<=25;j++)
    for (k=0; k<= 25;k++)
     for (l=maxdepth+1; l<= 25; rank[i][j][k][l++]=-1);   

  
  anzpossguesses = 0;
  finalguess[0]=-1;
  bestsum=100000;
  
  /* initializations */
  
  generateguess();
  /* Finally! Find a guess! */
  
  
  if (anzpossguesses==0) {
   /*No solution found, so drop restrictions...*/

   relax();

   memcpy(rank1,arank1,26);
   memcpy(rank2,arank2,26*26);
   memcpy(rank,arank,7*26*26*26);
   for (i=maxdepth+1;i<=25;rank1[i++]=-1);
   for (i=0;i<=25;i++)
    for(j=maxdepth+1;j<=25;rank2[i][j++]=-1);
   for (i=0; i<wordlen-2; i++)
    for (j=0;j<=25;j++)
     for (k=0; k<= 25;k++)
      for (l=maxdepth+1; l<= 25; rank[i][j][k][l++]=-1);   
   generateguess();
   /* ... and try again */
  }

  saveandexit();
  /* This is necessary for (at least) specialmode when less than 6
     guesses are possible. */
}
