Относительно простой метод сжатия данных может быть выполнен путём создания так называемых деревьев Хаффмана для файла и используется для его сжатия и распаковки данных в нём. Для большинства приложений используются бинарные деревья Хаффмана (например, каждый узел является либо листом, либо имеет ровно два подузла). Можно, однако, построить деревья Хаффмана с произвольным числом поддеревьев (например, троичных или, в общем случае, \textbf{N}-ичных деревьев). Дерево Хаффмана для файла, содержащего \textbf{Z} разных символов имеет \textbf{Z} листьев. Путь от корня к листу, который представляет определенный символ, определяет кодировку, и каждый шаг на пути к листу определяет кодировку (которая может быть \textbf{0}, \textbf{1}, ..., \textbf{(N-1)}). Путём размещения часто встречающихся символы ближе к корню, и менее часто встречающихся символов дальше от корня, и достигается желаемое сжатие. Строго говоря, такое дерево будет деревом Хаффмана, только если в результате кодирования будет использовано минимальное число \textbf{N}-ичных символов для кодирования заданного файла. В этой задаче мы будем рассматривать только деревья, где каждый узел является либо внутренним узлом либо листом кодирования символов и нет изолированных листьев, которые не кодируют символ. На рисунке ниже показан пример троичного дерева Хаффмана, символы '\textbf{a}' и '\textbf{е}' кодируются с помощью одной троичного символа; менее часто встречающиеся символы '\textbf{s}' и '\textbf{p}' кодируются с помощью двух троичных символов и наиболее редко встречающиеся символы '\textbf{x}', '\textbf{q}' и '\textbf{y}' кодируются с помощью трех троичных символов каждый. \includegraphics{https://static.e-olymp.com/content/44/440d9c2a24e56ece64e196a6dd41ace76285106e.jpg} Конечно, если мы хотим, чтобы можно развернуть список \textbf{N}-ичных символов потом обратно, важно знать, какое дерево используется для сжатия данных. Это можно сделать несколькими способами. В этой задаче мы будем использовать следующий метод: потоку входных данных будет предшествовать заголовок, состоящий из закодированных значений символов \textbf{Z}, находящихся в исходном файле в лексикографическом порядке. Зная количество входных символов \textbf{Z}, значение \textbf{N}, обозначающее "\textbf{N}-арность" дерева Хаффмана и сам заголовок, необходимо найти первичное значение закодированных символов. \InputFile Входные данные начинаются с целого числа \textbf{T}, расположенного в отдельной строке и обозначающего количество последующих тестовых случаев. Далее задано каждый из \textbf{T} тестовых случаев, каждый из которых расположен в \textbf{3}-х строках следующим образом: \begin{itemize} \item Количество различных символов в тестовом случае \textbf{Z} (\textbf{2} ≤ \textbf{Z} ≤ \textbf{20}); \item Число \textbf{N}, обозначающее "\textbf{ N} -арность" дерева Хаффмана (\textbf{2} ≤ \textbf{N} ≤ \textbf{10}); \item Строка, представляющая заголовок полученного сообщения, каждый символ будет цифрой в диапазоне \textbf{\[0, (N-1)\]}. Эта строка будет содержать меньше \textbf{200} символов. \end{itemize} \textit{\textbf{Примечание:}} Хотя и редко, но это возможно для заголовка, чтобы иметь несколько толкований при расшифровке (например, для заголовка '\textbf{010011101100}', и значениях \textbf{Z = 5} и \textbf{N = 2}). Гарантируется, что во всех предлагаемых во входных данных тестовых случаях, имеется единственное решение. \OutputFile Для каждого из \textbf{T} тестовых случаев вывести \textbf{Z} строк, дающих декодированную версию каждого из \textbf{Z} символов в порядке возрастания. Используйте формат \textbf{оригинал->кодировка}, где \textbf{оригинал} -- это десятичное число в диапазоне \textbf{\[0, (Z-1)\]} и соответствующая кодированная строка кодированных цифр для этих символов (каждая цифра ≥ \textbf{0} и < \textbf{N}).