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

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

int ff(int z, int kolko) {
  int i,sum=0;
  
  for (i=0;i<kolko;i++) sum+=f[z+i]*(i+1);
  return sum;
}

void wr(int l, int r, int q) {
  int i;
  
  if (q==0) return;
  if (q>2) wr(A[l][q].p,l,q-1); else wr(0,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);
    for (i=1;i<=L;i++) scanf("%d ",&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;
      for (p=1;p<i;p++) {
        xx = A[p][j-1].sum+ff(p+1,i-p);
        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;
}