Дерево Хаффмана
Відносно простий метод стиснення даних може бути виконаний шляхом створення так званих дерев Хаффмана для файла і використовується для його стисненн та розпаковки даних у ньому. Для більшості додатків використовуються бінарні дерева Хаффмана (наприклад, кожен вузол є або листком, або має рввно два підвузла). Можна, проте, побудувати дерева Хаффмана з довільним числом піддерев (наприклад, трійкових або, у загальному випадку, N-кових дерев).
Дерево Хаффмана для файла, який містить Z різних символів має Z листків. Шлях від кореня до листка, який подає певний символ, визначає кодування, і кожен крок на шляху до листка визначає кодування (яке може бути 0, 1, ..., (N-1)). Шляхом розміщення символів, які частіше зустрічаються, ближче до кореня, і символів, які рідше зустрічаються, подалі від кореня, і досягається бажане стиснення. Строго кажучи, таке дерево буде деревом Хаффмана, лише якщо у результаті кодування буде використано мінімальну кількість N-кових символів для кодування заданого файлу.
У цій задачі ми будемо розглядати лише дерева, у яких кожен вузол є або внутрішнім вузлом або листком кодування символів і немає ізольованих листків, які не кодують символ.
На рисунку нижче показано приклад трійкового дерева Хаффмана, символи 'a' та 'е' кодуються за допомогою одного трійкового символа; символи, які зустрічаються менш часто, 's' та 'p', кодуються за допомогою двох трійкови символів і символи, які найбільш рідко зустрічаютьщиеся, 'x', 'q' та 'y', кодуються за допомогою трьох трійкових символів кожен.
Звичайно, якщо ми хочемо, щоб можна було рогорнути список N-кових символів потім назад, важливо знати, яке дерево використовується для стиснення даних. Це можна зробити декількома способами. У цій задачі ми будемо викорситовувати наступний метод: потоку вхідних даних буде передувати заголовок, який складається з закодованих значень символів Z, які знаходяться у заданому файлі у лексикографічному порядку.
Знаючи кількість вхідних символів Z, значення N, яке позначає "N-арність" дерева Хаффмана та сам заголовок, необхідно знайти початкове значення закодованих символів.
Вхідні дані
Вхідні дані починаються з цілого числа T, розміщеного у окремому рядку і яке позначає кількість наступних тестових випадків. Далі задано кожен з T тестових випадків, кожен з яких розміщено у 3-х рядках наступним чином:
Кількість різних символів у тестовому випадку Z (2 ≤ Z ≤ 20);
Число N, яке позначає " N -арність" дерева Хаффмана (2 ≤ N ≤ 10);
Рядок, який подає заголовок отриманого повідомлення, кожен символ буде цифрою у діапазоні [0, (N-1)]. Цей рядок буде містити менше 200 символів.
Примітка: Хоча й рідко, але це можливо для заголовку, що буде декілька тлумачень при розшифровці (наприклад, для заголовку '010011101100', та значеннях Z = 5 і N = 2). Гарантується, що у всіх пропонованих у вхідних даних тестових випадках, існує єдиний розв'язок.
Вихідні дані
Для кожного з T тестових випадків вивести Z рядків, які дають декодовану версію кожного з Z символів у порядку зростання. Використовуйте формат оригінал->кодування, де оригінал – це десяткове число у діапазоні [0, (Z-1)] і відповідний кодований рядок кодованих цифр для цих символів (кожна цифра ≥ 0 і < N).