Иван хочет сделать бусы в подарок своей возлюбленной. Бусы — это замкнутая в цикл последовательность бусинок разных цветов. Иван называет бусы красивыми относительно разреза в точке между соседними бусинками, если цепочка бус, остающаяся после этого разреза, является палиндромом (читается одинаково в обе стороны).
У Ивана есть бусинки n цветов. Он хочет составить бусы, которые будут являться красивыми относительно наибольшего числа разрезов, при этом он обязательно хочет использовать все имеющиеся бусинки. Помогите ему составить наиболее красивые бусы.
Выходные данные
В первой строке выведите единственное число — наибольшее количество красивых разрезов, которого можно добиться. Во второй строке выведите бусы, обладающие таким числом красивых разрезов.
Каждый цвет бусинок кодируется соответствующей строчной английской буквой (начиная с a), содержимое бус можно выводить начиная с любой позиции. Если правильных ответов несколько, разрешается вывести любой.
Примечание
В первом тесте бусы не могут иметь более одного красивого разреза. Пример бус с одним красивым разрезом приведен на картинке.
Во втором тесте бусы можно составить единственным образом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 2 1
|
1
abacaba
|
|
2
|
1
4
|
4
aaaa
|
|
3
|
2
1 1
|
0
ab
|