 | Эла очень любит читать, как и ее новые коллеги по DTL! В первый же день её работы в DTL коллега попросил её распределить книги по отсекам на книжной полке. |
\(n\) книг должны быть распределены по \(k\) отсекам на книжной полке (\(n\) нацело делится на \(k\)). Каждой книге можно сопоставить одну строчную латинскую букву от 'a' до 'y' включительно, которая является начальной буквой в названии книги.
Эла должна положить ровно \(\frac{n}{k}\) книг в каждый отсек. Отсеки пронумерованы от \(1\) до \(k\). Положив книги, для каждого отсека она возьмет ровно одну букву — MEX мультимножества букв, соответствующих книгам в этом отсеке, и затем объединит полученные буквы в одну строку. Первая буква итоговой строки — это буква MEX мультимножества букв в первом отсеке, вторая буква итоговой строки — это буква MEX мультимножества букв во втором отсеке, и так далее. Обратите внимание, что в ограничениях этой задачи MEX всегда может быть определен для любого мультимножества букв, соответствующих книгам, потому что 'z' не может являться начальной буквой в названиях книг.
Какую лексикографически наибольшую результирующую строку может получить Эла?
Строка \(a\) лексикографически больше строки \(b\) тогда и только тогда, когда выполняется одно из следующих условий:
- \(b\) является префиксом \(a\), но \(b \ne a\);
- в первой позиции, где \(a\) и \(b\) различаются, в строке \(a\) стоит буква, которая представлена в алфавите позже, чем соответствующая буква в \(b\).
MEX мультимножества букв – это первая в алфавите буква, которая не входит в это мультимножество. Например, если мультимножество букв содержит \(7\) букв 'b', 'a', 'b', 'c', 'e', 'c', 'f', то MEX этого мультимножества будет 'd', поскольку 'd' не содержится в мультимножестве, и все буквы, предшествующие 'd' в алфавите, а именно 'a', 'b' и 'c', содержатся в мультимножестве.
Выходные данные
Для каждого набора входных данных выведите строку длины \(k\), которая является лексикографически наибольшей строкой, которую может получить Эла.
Примечание
В первом наборе входных данных книги можно распределить по \(3\) отсекам как показано ниже:
- в первом отсеке находятся книги с индексами \(1, 2, 3, 7\): \(multiset_1 = \{\)'c', 'a', 'b', 'd'\(\}\) \(\rightarrow\) \(MEX(multiset_1) =\) 'e'
- во втором отсеке находятся книги с индексами \(4, 5, 6, 9\) : \(multiset_2 = \{\)'c', 'c', 'a', 'b'\(\}\) \(\rightarrow\) \(MEX(multiset_2) =\) 'd'
- в третьем отсеке находятся книги с индексами \(8, 10, 11, 12\): \(multiset_3 = \{\)'a', 'a' , 'a', 'c'\(\}\) \(\rightarrow\) \(MEX(multiset_3) =\) 'b'
Следовательно, ответ 'edb'. Можно доказать, что Эла никак не может расположить книги так, чтобы в результате получилась лексикографически большая строка.
