Недавно на уроке во время контрольной Мария Ивановна перехватила записку от Саши к Оле. Мария Ивановна очень хочет знать, что в записке, но, к сожалению, записка зашифрована. Мария Ивановна знает, что её ученики для шифровки заменяют каждую букву исходного сообщения на какую-то другую. Замена происходит таким образом, что одинаковые буквы всегда заменяются одной и той же буквой, а разные — разными.
Мария Ивановна подозревает, что записка — это ответы к контрольному тесту (ведь её длина случайно оказалась равной длине строки с правильными ответами). Однако она знает, что ответы Саши не обязательно полностью правильны. На каждый вопрос возможен один из K вариантов ответа. Естественно, Мария Ивановна знает правильные ответы.
Мария Ивановна решила расшифровать записку таким способом, чтобы максимизировать количество правильных ответов Саши. Однако, она очень занята, поэтому попросила Вас помочь ей в этом пустяковом деле.
Выходные данные
В первой строке выведите единственное число — максимально возможное количество правильных ответов у Саши.
Во второй строке выведите расшифровку — строчку длины K, где по порядку для каждой буквы из шифра учеников указано, какому ответу она соответствует.
Если несколько расшифровок дают правильный ответ, выведите любую.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 2
aaabbbaaab
bbbbabbbbb
|
7
ba
|
|
2
|
10 2
aaaaaaabbb
bbbbaaabbb
|
6
ab
|
|
3
|
9 4
dacbdacbd
acbdacbda
|
9
cdba
|