#include <stdio.h>

#define id if (0)

#define INF 1000000000l

int main()
{ 
int TEST,test;
int K,L,k,l,i;
int tab[92][92][92];
int co[92][92];
int min,koszt;
int F[100];
char keys[100],letters[100];
int ile[100],ktory;


  scanf("%i",&TEST);
  for (test=1;test<=TEST;test++)
  {
    printf ("Keypad #%i:\n",test);
    scanf("%i %i",&K,&L);
    scanf("%s %s",keys,letters);
    for (l=1;l<=L;l++) scanf ("%i",&F[l]);
    for (k=0;k<=K;k++)
      for (l=0;l<=L;l++)
        for (i=0;i<=K;i++)
          tab[l][k][i]=INF;
    tab[1][1][1]=F[1];
    for (k=2;k<=K;k++) tab[k][k][1]=F[k]+tab[k-1][k-1][1];
    for (l=2;l<=L;l++)
      for (k=1;k<=K && k<l;k++)
      {
       if (k>1)
         {
   		  min=INF;
		  for (i=1;i<l;i++) 
            if (tab[l-1][k-1][i]<=min)
		  	  min=tab[l-1][k-1][i];
           tab[l][k][1]=min+F[l];
           if (tab[l][k][1]>=INF) tab[l][k][1]=INF;
         }
        for (i=2;i<=l;i++) tab[l][k][i]=tab[l-1][k][i-1]+F[l]*i;
        for (i=2;i<=l;i++) if (tab[l][k][i]>=INF) tab[l][k][i]=INF;
      }
 /*teraz trzeba znalezc najlepsze*/
id for (l=1;l<=L;l++)
   {
     for (k=1;k<=K;k++) if (tab[l][k][1]==INF) printf("------");
     else printf ("%6i",tab[l][k][1]);
     putchar ('\n');
   }
    l=L;k=K;
    min=tab[l][k][1];
    for (i=2;i<=l;i++)
     if (tab[l][k][i]<min) 
      min=tab[l][k][i];
    koszt=min;
    while (k>0)
	{
      ktory=l;
      while (tab[l][k][ktory]!=koszt) ktory--;
id printf ("k: %i, l; %i,koszt: %i\n",k,l,koszt); 
      ile[k]=ktory;
      for (i=1;i<=ktory;i++) koszt-=F[l-ktory+i]*i;
      k--;
      l-=ktory;
    }
id for (i=1;i<=K;i++) printf ("ile[%i]: %i\n",i,ile[i]);
    l=0;
    for (k=1;k<=K;k++)
    {
 	  printf ("%c: ",keys[k-1]);
      for (i=0;i<ile[k];i++) putchar(letters[l++]);
      putchar ('\n');
    }
    putchar('\n');
  }
  return 0;
}