허프만 트리

데이터를 압축하는 비교적 간단한 방법으로 허프만 트리(Huffman tree)가 있다. 허프만 트리를 이용하면 파일에 들어 있는 데이터를 손쉽게 압축하고 다시 풀 수 있다.

많은 프로그램은 이진(binary) 허프만 트리를 사용한다. 이진 허프만 트리에서 각 노드는 리프이거나 정확히 두 개의 자식을 갖는다. 이 문제에서는 이를 일반화하여, 각 내부 노드가 정확히 $N$개의 자식을 갖는 $N$진(N-ary) 허프만 트리를 다룬다.

파일에 서로 다른 글자가 $Z$개 있으면 리프 노드의 개수도 $Z$개이다. 루트에서 어떤 리프까지 내려가는 경로에 적힌 숫자들이 그 글자의 인코딩이 된다. 자식으로 내려가는 각 간선에는 $0$부터 $N-1$까지의 숫자가 붙어 있다.

자주 쓰는 글자를 루트 가까이에, 드물게 쓰는 글자를 멀리 두면 압축 효율이 올라간다. 즉, 한 파일을 인코딩하는 데 필요한 $N$진 심볼의 총 개수가 최소가 되도록 만든 트리가 허프만 트리이다.

이 문제에서 다루는 허프만 트리의 모든 노드는 내부 노드이거나 글자 하나를 인코딩하는 리프 노드이다. 어떤 글자도 인코딩하지 않는 리프(dangling leaf)는 존재하지 않으며, 따라서 모든 내부 노드는 정확히 $N$개의 자식을 갖는다.

예를 들어 $N=3$일 때, 자주 쓰는 글자는 심볼 한 개로, 덜 쓰는 글자는 심볼 두 개로, 아주 드문 글자는 심볼 세 개로 인코딩될 수 있다.

디코딩을 하려면 인코딩에 사용한 트리를 알아야 하므로 트리를 저장해 두어야 한다. 이 문제에서는 트리를 다음과 같이 저장한다. 서로 다른 $Z$개의 글자를 각각 정수 $0, 1, \dots, Z-1$로 나타내고, 이 글자들을 오름차순으로 한 번씩 늘어놓은 파일을 인코딩한 결과 문자열을 저장한다. 즉 저장된 문자열은 글자 $0$의 인코딩, 글자 $1$의 인코딩, $\dots$, 글자 $Z-1$의 인코딩을 차례대로 이어 붙인 것이다.

$N$과 위 방식으로 저장된 문자열이 주어졌을 때, 각 글자가 어떤 심볼 열로 인코딩되는지 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음과 같이 세 줄로 이루어진다.

• 첫째 줄: 파일에 들어 있는 서로 다른 글자의 개수 $Z$ ($2 \le Z \le 20$)
• 둘째 줄: 허프만 트리의 arity $N$ ($2 \le N \le 10$). 트리는 $N$진 트리이며, $N=2$이면 이진, $N=3$이면 삼진 트리이다.
• 셋째 줄: 모든 글자를 오름차순으로 한 번씩 늘어놓은 파일을 인코딩한 결과 문자열. 길이는 $200$을 넘지 않으며, 각 문자는 $0$부터 $N-1$까지의 숫자이다.

같은 문자열이 서로 다른 트리에 대응될 수도 있다. 예를 들어 $Z=5$, $N=2$일 때 문자열 $010011101100$은 여러 트리에 대응될 수 있다. 그러나 이 문제에서는 답이 유일하게 결정되는 경우만 입력으로 주어진다.

각 테스트 케이스마다 $Z$줄을 출력한다. 각 줄은 글자->인코딩 형식이며, 글자는 $0$부터 $Z-1$까지의 정수, 인코딩은 그 글자가 허프만 트리에서 대응되는 심볼 열이다. 글자는 $0, 1, \dots, Z-1$ 순서대로 출력한다.