#include <stdio.h>


long long cost[200][200];
int opt[200][200];
char keys[200];
char letters[200];
int freq[200];

int K,L;

void solve(void)
  {
  int i,j,k,l,p;
  int optp;
  long long pen,pomp,minp;
  for(i=0;i<K;cost[L][i++]=0);
  for(i=0;i<L;cost[i++][K]=0);
  for(i=L-1;i>=0;i--)
    for(j=K-1;j>=0;j--)
      {
      minp=((long long)100)*100000;
      pen=0;
      optp=0;
      p=1;
      while(1)
        {
        if(i+p>L) break;
        pen+=((long long)p)*freq[i+p-1]; 
        pomp=pen+cost[i+p][j+1];
        if(pomp<minp)
          {
          optp=p;
          minp=pomp;
        }
        p++;
      }
      if(j==K-1)
        {
        cost[i][j]=pen;
        opt[i][j]=p-1;
      }else
        {
        cost[i][j]=minp;
        opt[i][j]=optp;
      }
    }
  j=0;k=0;
  for(i=0;i<K;i++)
    {
    printf("%c: ",keys[i]);
    k=j+opt[j][i];
    while(j!=k) 
      putchar(letters[j++]);
    putchar('\n');
  }
}

int main(void)
  {
  int z,i;
  scanf("%d",&z);
  for(i=1;i<=z;i++)
    {
    int j;
    printf("Keypad #%d:\n",i);
    scanf("%d %d",&K,&L);
    scanf("%s",keys);
    scanf("%s",letters);
    for(j=0;j<L;j++)
     scanf("%d",freq+j);
    solve();  
    putchar('\n');
  }
  return 0;
}