I-Keyboard

휴대전화의 옛날 방식 키패드로 문자를 입력하는 일은 번거롭습니다. 키의 수가 적어서 대부분의 키에 여러 글자가 배정되어 있고, 한 글자를 입력하려면 같은 키를 여러 번 눌러야 하는 경우가 많기 때문입니다. 일반적인 키패드에는 열두 개의 키가 있으며, 그중 여덟 개만으로 영어 알파벳 26글자를 입력합니다. 표준 배열에서는 글자가 다음과 같이 묶여 있습니다.

 1         2 abc      3 def 4 ghi     5 jkl      6 mno 7 pqrs    8 tuv      9 wxyz *         0 space    #

한 키에서 묶음의 첫 번째 글자는 한 번, 두 번째 글자는 두 번, 그다음 글자는 그만큼 더 눌러야 합니다. 이 배열은 글자를 키에 고르게 나누지만, 각 글자가 얼마나 자주 쓰이는지는 고려하지 않습니다. 어떤 글자는 다른 글자보다 훨씬 자주 쓰이므로, 자주 쓰이는 글자가 세 번째나 네 번째 자리에 놓이면 입력 비용이 커집니다. 예를 들어 영어에서 자주 쓰이는 "s"는 표준 배열에서 네 번을 눌러야 합니다. 아래처럼 글자의 사용 빈도에 맞춘 배열이라면 보통의 문장을 입력하기가 훨씬 편합니다.

 1         2 abcd     3 efg 4 hijk    5 lm       6 nopq 7 rs      8 tuv      9 wxyz *         0 space    #

주어진 글자 빈도에 대해 가장 좋은 배열을 구하세요. 사용자가 혼란스러워하지 않도록 글자는 원래의 (알파벳) 순서를 유지해야 하지만, 연속한 글자 몇 개든 한 키에 배정할 수 있습니다.

첫 줄에 테스트 케이스의 개수를 나타내는 양의 정수 T가 주어집니다.

각 테스트 케이스의 첫 줄에는 공백 하나로 구분된 두 정수 K와 L(1 ≤ K ≤ L ≤ 90)이 주어집니다. K는 키의 개수, L은 그 키들에 배정할 글자의 개수입니다.

다음 줄에는 키의 이름을 나타내는 정확히 K개의 문자가, 그다음 줄에는 글자의 이름을 나타내는 정확히 L개의 문자가 주어집니다. 모든 키 이름과 글자 이름은 ASCII 코드 33부터 126까지의 출력 가능한 문자입니다. 키 이름끼리는 서로 다르고 글자 이름끼리도 서로 다르지만, 같은 문자가 키 이름과 글자 이름으로 동시에 쓰일 수 있습니다.

그 뒤로 정확히 L개의 줄이 이어지며, i번째 줄에는 (주어진 순서대로) i번째 글자의 빈도를 나타내는 양의 정수 Fi가 있습니다. 값이 클수록 자주 쓰이는 글자입니다. 어느 빈도도 100000을 넘지 않습니다.

각 테스트 케이스마다, 전체 입력 비용이 가장 낮은 최적의 키보드를 만드세요. 한 글자의 비용은 그 글자의 빈도에 키 위에서의 위치(그 키의 첫 번째 글자는 1, 두 번째는 2, …)를 곱한 값이고, 전체 비용은 모든 글자의 비용을 더한 값입니다. 글자는 주어진 순서를 유지한 채 연속한 묶음으로 나뉘며, 묶음 하나가 키 하나에 대응합니다.

형식적으로, 다음 조건을 만족하는 위치 P1, P2, …, PL을 찾으세요.

• P1 = 1
• 모든 i > 1에 대해 Pi = Pi−1 + 1 또는 Pi = 1
• Pi = 1인 값은 많아야 K개
• 전체 비용 SP = Σ (1 ≤ i ≤ L) Fi · Pi가 최소
• 최소 비용을 갖는 여러 배열 중에서는, 마지막 키에 가능한 한 많은 글자를 배정하고, 그다음으로 그 앞 키에 많이 배정하는 식으로 정해진 배열을 선택합니다. (같은 전체 비용을 갖는 다른 유효한 배열 Q에 대해, J > M인 모든 J에서 PJ = QJ이고 PM > QM인 지표 M이 존재한다는 뜻입니다.)

K ≤ L이므로 최적의 키보드는 항상 K개의 키를 모두 사용하며, 따라서 모든 키에는 글자가 적어도 하나 배정됩니다.

각 테스트 케이스에 대해 먼저 "Keypad #I:" 한 줄을 출력합니다. 여기서 I는 1부터 시작하는 테스트 케이스 번호입니다. 이어서 입력 순서대로 키마다 한 줄씩 정확히 K줄을 출력합니다. 각 줄에는 그 키의 문자, 콜론, 공백 하나, 그리고 그 키에 배정된 글자들을 구분 기호 없이 이어 붙여 씁니다. 연속한 테스트 케이스 사이에는 빈 줄 하나를 출력합니다.