/* Problem 5--Substitution Cipher
   A way that's not too bad is to go through the words and build a table
   to guess alphabetical order between letters.  Then go through the
   table to see which letters are guessable. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int table[26][26], wct, letters;
FILE *in, *out;
char words[20][22], decode[26], message[52];

int main (int argc, char **argv);
void FillTable (void);

int main (int argc, char **argv) {

  int cases, i, j, good;

 in = fopen ("prob5.in","r");
 out = fopen ("prob5.out","w");
 fscanf (in,"%d",&cases); /* get cases */
 for (i=0; i < cases; i++) {
  fscanf (in,"%d %d",&letters,&wct); /* get alphabet and words */
  memset (table,-1,sizeof table); /* Initialize table with -1's */
  fgets (words[0],22,in);
  for (j=0; j < wct; j++) {
   fgets (words[j],22,in);
   words[j][strlen(words[j])-1] = 0;
  }
  FillTable ();
  fgets (message,52,in);
  message[strlen(message)-1] = 0;
  good = 1;
  for (j=0; good && j < (int)strlen (message); j++) {
   if (message[j] >= 'a' && message[j] <= 'a'+letters-1) {
    if (decode[message[j]-'a'] == '?') good = 0; /* unknown character */
    else message[j] = decode[message[j]-'a'];
   }
  }
  if (good) fprintf (out,"%s\n",message);
  else fprintf (out,"Message cannot be decrypted.\n");
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* The table is filled as follows.  table[i][j] is 1 if i is known to
   precede j.  It is 0 if i is known not to precede j.  It is -1 if this
   information is not available.  The letter that 0 things precede must
   be a.  The letter that 1 thing precedes must be b, and so forth. */
void FillTable (void) {

  int i, j, k, ii, jj, kk, ch;

 for (i=0; i < letters; i++) table[i][i]=0; /* no letter precedes self*/
 for (i=0; i < wct-1; i++)
  for (j=i+1; j < wct; j++) {/*skip if one word is a prefix of another*/
   if (memcmp (words[i],words[j],strlen (words[i]))==0) continue;
   for (k=0; words[i][k]==words[j][k]; k++); /* find first diff letter*/
   table[words[i][k]-'a'][words[j][k]-'a'] = 1; /* set table */
   table[words[j][k]-'a'][words[i][k]-'a'] = 0;
  }
 do { /* Apply transitive closure to this table */
  ch = 0;
  for (ii=0;ii<letters;ii++)
   for (jj=0;jj<letters;jj++)
    for (kk=0;kk<letters;kk++)
     if (table[ii][jj] == 1 && table[jj][kk]==1 && table[ii][kk] != 1) {
      table[ii][kk] = 1;
      table[kk][ii] = 0;
      ch = 1;
     }
 } while (ch);
 memset (decode,'a',sizeof decode); /* set all letters to a */
 for (j=0; j < letters; j++)
  for (i=0; i < letters; i++) {
   if (table[i][j]==-1) { /* if we don't know how many letters precede*/
    decode[j]='?';
    break;
   }
   decode[j] += table[i][j]; /* increment through alphabet */
  }
}