#include <stdio.h>

int f[100][100], tab[100][100], p[100][100], freq[100], podzial[100];
char klawisze[120], znaki[120];
int d, i, j, k, min, n, K, L, t;

int main(void)
{
 scanf("%d", &n);
 for(d = 1; d <= n; d++)
 {
  scanf("%d %d", &K, &L);
  scanf("%s %s", klawisze, znaki);
  for(i = 0; i < L; i++)
  {
   scanf("%d", &freq[i]);
   tab[i][i] = freq[i];
  } 
   
  for(i = 0; i < L; i++)
   for(j = i + 1; j < L; j++)
    tab[i][j] = tab[i][j -1] + (j - i + 1) * freq[j];
    
  for(i = 0; i < L; i++)
   f[1][i] = tab[0][i];
 ////////////////////////////////////////  
//   for(i = 0; i < L; i++)
//{
// for(j = i ; j < L; j++)
//  printf("%8d ", tab[i][j]);
//  printf("\n");
//}
 ////////////////////////////////////////  
   
  for(i = 2; i <= K; i++)
  {
   for(j = i - 1; j < L; j++)
   {
    f[i][j] = 0x7fffffff;
    for(k = i - 2; k <= j - 1; k++)
     if (f[i][j] > f[i - 1][k] + tab[k + 1][j])
     {
      f[i][j] = f[i - 1][k] + tab[k + 1][j];
      p[i][j] = k;
     }
   }
  } 
  
  podzial[K - 1] = L - 1;
  for (i = K - 2; i >= 0; i--)
   podzial[i] = p[i + 2][podzial[i + 1]];
   
  t = 0;
  printf("Keypad #%d:\n", d);
  for(i = 0; i < K; i++)
  {
   printf("%c: ", klawisze[i]);
   for(j = t; j <= podzial[i]; j++)
    printf("%c", znaki[j]);
   t = j;
   printf("\n");
  }
  
  printf("\n");
//  for(i = 0; i < K; i++) 
//   printf("%d ", podzial[i]);
 } 
 return 0;
}