program ikeyb;

const
  Infinity = $3FFFFFFF;
  
var
  F: array [1..90] of Integer;
  FreqFrom: array [1..90] of Integer;
  Cost: array [1..90, 1..90] of Integer;
  Num: array [1..90, 1..90] of Integer;
  I: Integer;
  J: Integer;
  K: Integer;
  L: Integer;
  M: Integer;
  N: Integer;
  SetNum: Integer;
  T: Integer;
  Keys: string [90];
  Letters: string [90];
  
begin
  SetNum := 0;
  Read(T);
  while T <> 0 do
  begin
    Dec(T);
    Readln(K, L);
    Readln(Keys);
    Readln(Letters);
    for I := 1 to L do 
      Read(F[I]);
    FreqFrom[L] := F[L];
    for I := L - 1 downto 1 do
      FreqFrom[I] := FreqFrom[I + 1] + F[I];
    Cost[K, L] := F[L];
    Num[K, L] := 1;
    for I := L - 1 downto 1 do
    begin
      Cost[K, I] := Cost[K, I + 1] + FreqFrom[I];
      Num[K, I] := Num[K, I + 1] + 1;
    end;
    for I := K - 1 downto 1 do
      for J := 1 to L do
      begin
        Cost[I, J] := Infinity;
	N := 0;
	for M := 1 to L - J do
	begin
	  Inc(N, M * F[J + M - 1]);
	  if N + Cost[I + 1, J + M] <= Cost[I, J] then
	  begin
	    Cost[I, J] := N + Cost[I + 1, J + M];
	    Num[I, J] := M;
	  end;
	end;        
      end;
    Inc(SetNum);
    Writeln('Keypad #', SetNum, ':');
    J := 1;
    for I := 1 to K do
    begin
      Write(Keys[I], ': ');
      for M := J to J + Num[I, J] - 1 do
        Write(Letters[M]);
      Writeln;
      Inc(J, Num[I, J]);
    end;
    Writeln;
  end;
end.