#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <assert.h>
#include <iostream.h>

int main()
{
  long ilosc_testow;
  char klawisze[91];
  char znaki[91];
  //int prop[91][91][91];
  int ilosc_znakow[91][91];
  long wartosc[91][91];
  long czestosc[91];
  int l,k,i;	  

  scanf("%ld\n", &ilosc_testow);
  for (int it=1; it <=ilosc_testow; it++)
  {
    cin >> k >> l;
    cin >> klawisze;
    cin >> znaki;
    for (i=1;i<=l;i++)
      cin >> czestosc[i];
    
    wartosc[1][1]=czestosc[1];
    //prop[1][1][1]=1;
    //int suma = czestosc[1];
	for (i=2;i<=l;i++)
      {
	//prop[1][i][1]=i;
	ilosc_znakow[1][i]=i;
	//suma+=czestosc[i];
	wartosc[1][i]=wartosc[1][i-1]+czestosc[i]*i;
      };

    // i - ilosc klawiszy
    long o1;
    int j,nrmin,nr,cp;
    for (i=2;i<=k;i++)
      {
	for (j=i; j<=l; j++) // j - ilosc liter
	  {
	    o1=wartosc[i-1][j-1]+czestosc[j];
	    nrmin=1;
	    cp=czestosc[j];	
	    int suma=cp;
	    for (nr=2; nr<=j-i+1; nr++)
              {
		suma += czestosc[j-nr+1];
		cp += suma;
		if ((wartosc[i-1][j-nr]+cp)<o1)
		  {
		    o1=wartosc[i-1][j-nr]+cp;
		    nrmin=nr;
		  }
		}
	      wartosc[i][j]=o1;
	      ilosc_znakow[i][j]=nrmin;
	  }
 
      }
    // wynik;
    int nakl[91];
    int pozostalo=l;
    for (i=k; i>0; i--)
      {
	nakl[i]=ilosc_znakow[i][pozostalo];
	pozostalo-=nakl[i];
      }
    cout << "Keypad #" << it << endl;
    int wypisano=0;
    for (i=1; i<=k; i++)
      {
	cout << klawisze[i-1] << ": ";
        for (j=1; j<=nakl[i]; j++)
	    cout << znaki[wypisano++];
	cout << endl; 	 	
      }
  }

  return 0;
}