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

int c_ulohy = 0, p_uloh;
char keybs[100], letters[100];
int prisarr[100];

#define MAXINT 2000000000
#define MAX(a,b) ((a)>(b)?(a):(b))

int pole[100][100];
int tmpcnt[100][100], cnt[100];
int prisel[100][100];

int main(void)
{
  scanf("%d\n", &p_uloh);
  for  (c_ulohy=0; c_ulohy < p_uloh; c_ulohy++) {
    int i,j,k,val, minv, pp;
    int K,L;
    scanf("%d %d\n", &K, &L);
/*    printf("keybs: " );*/
    for (i=0; i<K; i++) {
      scanf( "%c", &(keybs[i]));
/*      printf( "%c", keybs[i]);*/
    }

    scanf("\n");
/*    printf("keybs: " );*/
    for (i=0; i<L; i++) { 
      scanf( "%c", &(letters[i]));
/*      printf( "%c", letters[i] );*/
    }
    scanf("\n");  
/*    printf("letters: " );*/
    for (i=0; i<L; i++) {
      scanf( "%d\n", &(cnt[i]));
/*      printf( "%d ", cnt[i] );*/
    }
    j = 0;      
    for (i=0;i<L;i++) {
      j += cnt[i]*(i+1);
    }
    for (i=0;i<L;i++)
      pole[0][i]=j;

    for (i=0;i<L;i++) {
      val = 0;
      tmpcnt[i][i]=0;
      for (j=i;j<L;j++) {
        val += cnt[j]*(j-i+1);
        tmpcnt[i][j+1]=val;
	/*	printf("%d - ", val);*/
      }
    }
          
    for (j=1;j<K;j++) {
      int minva = MAXINT;
      int lastpris;
      int max1 = MAX(L-K+j,1);
      int max = MAX(L-K+j+1,1);
      /*
      if ((max < L+1) && (max > 1))
	pole[j-1][max-1] = pole[j-1][max-2];
      */
      for (i=0;i<max;i++) {
	int tov = (i==max1) ? i-1 : i; 
        minv = MAXINT;
        for (k=0 ;k<=tov;k++) {
          val = pole[j-1][k] - tmpcnt[k][L] + tmpcnt[k][i] + tmpcnt[i][L];
          if (val<minv) {
            minv = val;
            prisel[j][i] = k;
          }
        }
	pole[j][i] = minv;
	if (j==K-1 && minv<minva)
	{
	  minva = minv;
	  lastpris = i;
	  /*	  printf( "x:%d\n", i);*/
	}
      }
      if (j==K-1) {
        int po=K-1;
        prisarr[K]=L;
        prisarr[K-1] = lastpris;
	/*        printf("pr : %d\n", lastpris);*/
        while (po>0) {
          lastpris = prisel[po][lastpris];
          po--;
          prisarr[po] = lastpris;
        }  
      }
    }
    pp=0;
    printf("Keypad #%d:\n", c_ulohy+1);
    for (i=0; i<K; i++) {
      printf("%c: ", keybs[i]);
      while (pp<prisarr[i+1])
      {
        printf("%c", letters[pp]);
        pp++;
      }
      printf("\n");
    }  
    printf("\n");
    /*
    for (i=0;i<L;i++) {
      printf("%d\n", pole[K-1][i]);
    }
    */
  }
  return 0;
}