휴대폰이 일반화되면서 문자 메시지를 많이 주고 받는다. 휴대폰의 키패드에는 하나의 번호에 여러 개의 알파벳이 할당되어 있기 때문에 문자 메시지를 보낼 때 한 번호를 여러 번 눌러야 한다.

1   2 abc 3 def 4 ghi 5 jkl 6 mno 7 pqrs 8 tuv 9 xwyz *   0   #	1   2 abcd 3 efg 4 hijk 5 lm 6 nopq 7 rs 8 tuv 9 xwyz *   0   #
그림 1	그림 2

예를 들어, 'hello' 를 입력하기 위해서는 [그림 1]의 키패트에서는 '44 33 555 555 666' 처럼 13 번을 눌러야 한다. 즉, 'h' 를 입력하기 위해서 '4' 를 2 번 , 'e' 를 입력하기 위해서는 '3' 을 2 번 , 'l' 을 입력하기 위해서 '5' 를 3 번 눌러야 한다. 하지만 그림 2 의 키 패드에서는 '4 3 5 5 66' 처럼 6 번 누르면 된다.

민수는 문자 메시지를 보낼 때 키 패드를 가장 적게 누를 수 있도록 새로운 키 패드를 만들기 위해 고민 중이다. 먼저 민수는 문자 메시지를 보낼 때 사용되는 각 문자의 사용빈도에 따라 키 패드를 설계하기로 하고 각 문자의 사용빈도를 조새해두었다. 즉 문자 메시지를 보낼 때 평균적으로 알파벳 'a' 는 몇 번이나 사용되고, 알파벳 'b' 는 몇 번이나 사용되는가를 조사했다. 그리고 키 패드를 적게 누르도록 만들기 위해 알파벳 순서를 바꾸었더니 알파벳을 찾는데 어려움이 있어서 알파벳의 순서는 바꾸지 않도록 설계하려고 한다.

여러분이 민수가 조사한 각 문자의 사용빈도를 참고해서 아래의 처리 조건에 맞게 민수가 계획한 키패드를 만들어 보자.

입력 형식

• 첫 째줄에는 2 개의 수가 나온다.

  N

  키 패드에서 알파벳을 할당하기 위해 사용되는 키(번호)의 개수 ( 1 <= N <= 99)

  M

  키 패드에서 N 개의 키에 할당할 알파벳의 총 개수( 1 <= M <= 99)다.

• 둘째 줄에는 하나의 키를 대표하는 번호들(길이가 N 인 문자열)이 나온다. 일반 휴대폰에서는 10 개의 숫자 '0' 에서 '9' 가 그 키를 대표하지만 여기서는 아스키 코드로 변환했을 때 33 이상 126 이하인 문자를 모두 사용한다. 즉, 키 번호는 숫자가 아닐 수 있다.

• 셋째 줄에는 키 패드에 할당될 문자들(길이가 M 인 문자열)이 나온다. 일반 휴대폰에서는 알파벳 문자 전부가 키 패드의 각 키(번호)에 할당되어 있지만 여기서는 아스키 코드에 있는 문자 모두를 사용한다. 'adefxyz' 라고 주어지면 이 문자들을 N 개의 키(번호)에 나누어 할당해야 한다. 할당된 문자들은 알파벳이 아닐 수 있다.

• 넷째 줄부터 각 줄에는 셋째 줄에서 입력받은 문자열의 각 알파벳들의 사용빈도(F)를 입력받는다.(1 <= F <= 100000)

출력 형식

출력 예와 같이 P: T 형식으로 출력한다. P는 키번호이고 T 는 P 키에 할당된 알파벳 문자들이다.

입력과 출력의 예

입력

1 4
0
cdko
40179
90922
55086
17254

출력

0: cdko

입력

3 5
456
defgh
10
21
3
5
12

출력

4: d
5: efg
6: h

출력 1 과 출력 2 의 키 패드 배치 결과를 그림으로 표시하면 다음과 같다.

0 cdko	4 d 5 efg 6 h
출력 예 1	출력 예 2

출처: Central Europe 2000