Verilənlərin sıxışdırılmasının nisbətən sadə metodu fayl üçün Haffman ağacları adlanan ağacların qurulması yolu ilə yerinə yetirilə bilər və faylın sıxışdırılması və ondakı verilənlərin açılması üçün istifadə edilir. Bir çox proqramlar üçün Haffman ikilik ağacından istifadə edilir (məsələn, hər bir düyün nöqtəsi yarpaqdır, ya da iki altdüyünü vardır). Lakin ixtiyarı sayda altağacı olan Haffman ağacları qurmaq olar (məsələn, üçlük və ya ümumi halda \textbf{N}-lik ağaclar). \textbf{Z} müxtəlif simvollardan ibarət fayllar üçün Haffman ağacının \textbf{Z} yarpağı var. Kökdən müəyyən bir simvolu təyin edən yarpağa gedən yol və yarpağa gedən yolda hər bir addım (\textbf{0}, \textbf{1}, ..., \textbf{(N-1) o}la bilən) kodlaşdırmanı təyin edir. Tez-tez rast gəlinən simvolları kökə yaxın yerləşdirməklə və az rast gəlinənləri kökdən uzaq yerləşdirməklə arzu olunan sıxışdırmaya nail olunur. Daha dəqiq desək, belə ağac o zaman Haffman ağacı adlanır ki, verilmiş faylın kodlaşdırılması üçün minimal sayda \textbf{N}-lik simvollardan istifadə edilmiş olsun. Bu məsələdə biz yalnız o ağaca baxacağıq ki, hər bir düyün ya daxili düyün olsun, ya da simvolların kodlaşdırılması yarpağı olsun və simvolları kodlaşdırmayan izolyasiya edilmiş yarpaqları olmasın. Aşağıdakı şəkildə Hafmanın üçlük ağacına nümunə verilmişdir, '\textbf{a}' və '\textbf{е}' simvolları bir üçlük simvol ilə kodlaşdırılır. Az rast gəlinən '\textbf{s}' və '\textbf{p}' simvolları isə iki üçlük simvol ilə və daha az rast gəlinən '\textbf{x}', '\textbf{q}' və '\textbf{y}' simvollarının hər biri isə üç üçlük simvol ilə kodlaşdırılır. \includegraphics{https://static.e-olymp.com/content/44/440d9c2a24e56ece64e196a6dd41ace76285106e.jpg} Əlbəttə ki, biz istəyirik ki, B-lik simvollar siyahısını sonra geri açmaq imkanı olsun, sıxışdırmaq üçün hansı ağacın istifadə ediləcəyini bilmək lazımdır. Bunu bir neçə üsulla etmək olar. Bu məsələdə biz növbəti üsuldan istifadə edəcəyik: giriş verilənləri axınının əvvəlində cari faylda leksikoqrafik ardıcıllıqla saxlanılan \textbf{Z} simvolların kodlaşdırılmış qiymətlərini ehtiva edən başlıq veriləcək. \textbf{Z} giriş simvollarının sayını, Haffman ağacının \textbf{N}-lik olduğunu təyin edən \textbf{N} qiymətini və başlığın özünü bilərək kodlaşdırılmış simvolların ilkin qiymətini tapmaq tələb olunur. \InputFile Giriş verilənləri ayrı-ayrı sətirlərdə verilmiş və növbəti test hallarının sayını təyin edən \textbf{T} tam ədədi ilə başlayır. Sonra isə hər biri \textbf{3} sətirdə növbəti şəkildə yerləşmiş hər bir \textbf{T} test halları verilir: \begin{itemize} \item Test halında müxtəlif simvolların \textbf{Z} (\textbf{2} ≤ \textbf{Z} ≤ \textbf{20}) sayı; \item Haffman ağacının \textbf{N}-lik dərəcəsini təyin edən \textbf{N} ədədi; \item Alınan ismarışın başlığını əks etdirən sətir, hər bir simvol \textbf{\[0, (N-1)\]} rəqəm diapazonunda olacaq. Bu sətirdə \textbf{200}-dən az simvol olacaq. \end{itemize} \textit{\textbf{Tətbiq:}} Şifrələnmə zamanı bir neçə başa düşülən olması üçün heç olmazsa və nadir, lakin bu başlıq üçün mümkündür (məsələn, '\textbf{010011101100}' başlığı \textbf{Z = 5} və \textbf{N = 2} qiymətləri üçün). Giriş verilənlərində verilmiş bütün test hallarının yeganə həlli olduğuna zəmanət verilir. \OutputFile Hər bir \textbf{T} test halında hər bir \textbf{Z} simvolları üçün dekodlaşdırılmış versiyanı verən \textbf{Z} sayda sətirləri verməli. \textbf{orijinal->kodlaşdırma} formatından istifadə edin, \textbf{orijinal} -- \textbf{\[0, (Z-1)\]} diapazonunda və bu simvollar üçün kodlaşdırılmış rəqəmlərin kodlaşdırılmış sətrinə uyğun (hər bir rəqəm ≥ \textbf{0} və < \textbf{N}) onluq ədəddir.