#include <stdio.h>

int main(void) {
  int q,w,sum,pom,t,k,l,i,j,keypad;
  char s1[100],s2[100];
  int a[100][100],b[100][100];
  int f[100];
  
  scanf("%d ",&t);
  for (keypad=1;keypad<=t;keypad++) {
    printf("Keypad #%d:\n",keypad);
    scanf("%d %d ",&k,&l);
    scanf("%s ",s1);
    scanf("%s ",s2);
    for (i=0;i<l;i++)
       scanf("%d ",&f[i]);
    for (i=0;i<l+1;i++) {
       q=0;
       for(j=i;j<l;j++)
          q+=f[j]*(j-i+1);
       a[1][i]=q;
    }
    for (j=2;j<=k;j++)
       for (i=l;i>=0;i--) {
          q=a[j-1][i];
          sum=0;
          pom=i;
          for (w=i;w<l;w++) {
             sum+=f[w]*(w-i+1);
             if (sum+a[j-1][w+1] < q) {
                q=sum+a[j-1][w+1];
                pom=w+1;
             }
          }
          a[j][i]=q;
          b[j][i]=pom;
       }
    q=0;
    for (i=k;i>1;i--) {
      printf("%c: ",s1[k-i]);
      for (j=q;j<b[i][q];j++)
         printf("%c",s2[j]);
      printf("\n");
      q=b[i][q];
    }
    printf("%c: ",s1[k-1]);
    for (j=q;j<l;j++)
       printf("%c",s2[j]);
    printf("\n\n");
  }
  return 0;
}