У Монокарпа есть словарь из \(n\) слов, состоящих из первых \(12\) букв латинского алфавита. Слова пронумерованы от \(1\) до \(n\). Во всех парах соседних букв в слове буквы различны. Каждому слову \(i\) Монокарп сопоставил целое число \(c_i\) — как часто он использует это слово.
Монокарп хочет выбрать такой дизайн клавиатуры, чтобы он помог ему проще печатать некоторые слова. Клавиатуру можно описать, как последовательность из \(12\) первых букв латинского алфавита, где каждая буква от a до l встречается ровно один раз.
Слово можно легко напечатать на клавиатуре, если для каждой пары соседних символов в слове эти символы на клавиатуре тоже соседние. Оптимальность клавиатуры — это сумма \(c_i\) по всем словам \(i\), которые могут быть легко на ней напечатаны.
Помогите Монокарпу создать дизайн клавиатуры с максимальной оптимальностью.
Выходные данные
Выведите последовательность из \(12\) первых букв латинского алфавита, где каждая буква от a до l встречается ровно один раз, определяющую оптимальную клавиатуру. Если ответов несколько, выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
7 abacaba
10 cba
4 db
|
hjkildbacefg
|
|
2
|
1
100 abca
|
abcdefghijkl
|