#include <stdio.h>
#include <string.h>
#include <math.h>
#include <string.h>
#define MAX 91
#define NO -1 

int nkeys, nletters;
char keyname[MAX+1];
char letname[MAX+1];
int freq[MAX];
int min[MAX][MAX];
int how[MAX][MAX];
int cost[MAX][MAX];
int posit[MAX];

void debug (void)
{
	int i, j;
	
	printf("Nletters: %d Nkeys: %d\n", nletters, nkeys);
	printf("Min:\n");
	for (i=0; i<nkeys; i++)
	{
		for (j=0; j<nletters; j++)
			printf("%10d", min[i][j]);
		printf("\n");
	}
	printf("How: \n");
	for (i=0; i<nkeys; i++)
	{
		for (j=0; j<nletters; j++)
			printf("%5d", how[i][j]);
		printf("\n");
	}
	printf("Cost: \n");
	for (i=0; i<nletters; i++)
	{
		for (j=0; j<nletters; j++)
			printf("%10d", cost[i][j]);
		printf("\n");
	}
	

	printf("Pos: \n");
	for (i=0; i<nkeys; i++)
	{
		printf("%3d", posit[i]);
		printf("\n");
	}
}
	

void read_input(void)
{
	int i;
	
	scanf("%d%d", &nkeys, &nletters);
	scanf("%s", keyname);
	scanf("%s", letname);
	for (i=0; i<nletters; i++)
		scanf("%d", &freq[i]);
}

void init_cost (void)
{
	int i, j;
	
	for (i=0; i<nletters; i++)
		cost[i][i]=freq[i];
	for (i=0; i<nletters-1; i++)
		for (j=i+1; j<nletters; j++)
			cost[i][j]=cost[i][j-1]+freq[j]*(j-i+1);
}

void solve(void)
{
	int i, j;
	int pos, tmp;
	int a, b;
	
	init_cost();
	for (i=0; i<nletters; i++)
	{
		min[0][i]=cost[0][i];
		how[0][i]=i+1;
	}
	
	for (i=1; i<nkeys; i++)
		for (j=0; j<nletters; j++)
		{
			min[i][j]=NO;
			for (pos=1; pos<=nletters-1 && j-pos>=0; pos++)
				if (min[i-1][j-pos]!=NO)
				{
					tmp=min[i-1][j-pos]+cost[j-pos+1][j];
					if (min[i][j]==NO || tmp<=min[i][j])
					{
						min[i][j]=tmp;
						how[i][j]=pos;
					}
				}
		}
	
	b=nletters-1;
	for (a=nkeys-1; a>=0; a--)
	{
		for (i=b-how[a][b]+1; i<=b; i++)
			posit[i]=a;
		b=b-how[a][b];
	}
}

void write_output(void)
{
	int i, j;
	
	j=0;
	for (i=0; i<nkeys; i++)
	{
		printf("%c: ", keyname[i]);
		while (posit[j]==i && j<nletters)
		{
			printf("%c", letname[j]);
			j++;
		}
		printf("\n");
	}
}

int main()
{
	int z, zz;
	scanf("%d", &zz);
	for (z=0; z<zz; z++)
	{
		read_input();
		solve();
		/*debug();*/
		printf("Keypad #%d:\n", z+1);
		write_output();
		printf("\n");
	}
	return 0;
}