#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int price[95][95],totalP[95][95],pos[95][95],f[95],k,l; // tatolP[i][j]表示把前i个字母安排在j个键上的最小代价,pos[i][j]表示把1-i分成j段最后一个分段符的开始位置
char key_num[95],aphabet[95];
int keynum;//显示的键
//初始化price[][],price[i][j]表示将序列[i, j]安排到一个按键上的代价;
void SetPrice(){
    for(int i = 0 ; i < l ; i++){
            for(int j = i ; j < l ; j++){
                int z = 1;
                for(int k = i ; k <= j ; k++){
                    price[i][j] = z*f[k] + price[i][j];
                    z++;
                }
            }
        }
}

void DP(){
    for(int  i = 1 ; i <= l ; i++ ){
        totalP[i][1] = price[0][i-1];
    }
    for(int  i = 1 ; i <= k ; i++ ){
        totalP[i][i] = 0;
        for(int j = 0 ; j < i ; j++){
            totalP[i][i] += price[j][j];
        }
    }
    for(int i = 3 ; i <= l ; i++){
        for(int j = 2 ; j <= k && j < i; j++){
            totalP[i][j] = 2147483647;
            for(int m = j-1 ; m <= i-1 ; m++){
                if(totalP[m][j-1] + price[m][i-1] < totalP[i][j]){
                    totalP[i][j] = totalP[m][j-1] + price[m][i-1];
                    pos[i][j] = m;
                }
            }
        }
    }
}

void printf_result(int l,int k){
    if(k == 1){
        printf("%c: ",key_num[keynum++]);
        for(int i = 0 ; i < l ; i++){
            printf("%c",aphabet[i]);
        }
        printf("\n");
        return;
    }
//    if(l == k){
//        printf("%c: ",key_num[keynum++]);
//        for(int i = 0 ; i < l ; i ++){
//            printf("%c",aphabet[i]);
//        }
//        printf("\n");
//        return ;
//    }
    printf_result(pos[l][k],k-1);
    printf("%c: ",key_num[keynum++]);
    for(int  i = pos[l][k] ; i < l ; i++){
        printf("%c",aphabet[i]);
    }
    printf("\n");
}
int main()
{
    int n;
    scanf("%d",&n);
    int x = 1;
    while(x <= n){

        memset(price,0,sizeof(price));
        memset(totalP,0,sizeof(totalP));
        memset(pos,0,sizeof(pos));
        keynum = 0;
        scanf("%d %d",&k,&l);
        int i;
        scanf("%s",key_num);
        scanf("%s",aphabet);
        for(i = 0 ; i < l ; i++){
            scanf("%d",&f[i]);
        }

        SetPrice();
         DP();
         printf("Keypad #%d:\n",x);
        printf_result(l,k);
        printf("\n");
        x++;
    }
    return 0;
}