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

int T, tt;
int K,L,i,j,xx,p,fff;
char keys[100],letters[100];
int f[100],fsum[100];
typedef struct { int p; int sum; } oook;
oook A[100][100];

void wr(int l, int r, int q) {
  int i;
  
  if (q==0) return;
  wr(A[l][q-1].p,l,q-1);
  
  printf("%c: ",keys[q-1]);
  for (i=l+1;i<=r;i++) printf("%c",letters[i-1]);
  printf("\n");
  return;
}

int main() {
  scanf("%d",&T);
  for (tt=1;tt<=T;tt++) {
    printf("Keypad #%d:\n",tt);
    scanf("%d %d ",&K,&L);
    scanf("%s ",keys);
    scanf("%s ",letters);
    fsum[0]=0;
    for (i=1;i<=L;i++) {
      scanf("%d ",&f[i]);
      fsum[i]=fsum[i-1]+f[i];
    }
    
    for (j=1;j<=K;j++) { A[1][j].sum=f[1]; A[1][j].p=0; }
    for (i=2;i<=L;i++) {
      A[i][1].sum=A[i-1][1].sum+f[i]*i;
      A[i][1].p=0;
    }
    for (j=2;j<=K;j++) for (i=2;i<=L;i++) {
      A[i][j].sum=999999999;
      fff=0;
      for (p=i-1;p>=1;p--) {
        fff+=(fsum[i]-fsum[p]);
        xx = A[p][j-1].sum+fff;
        if (xx <= A[i][j].sum) {
          A[i][j].sum=xx;
          A[i][j].p=p;
        }
      }
    }
    
    wr(A[L][K].p,L,K);
    printf("\n");
  }
  
  return 0;
}