Расшифровка

Недавно на уроке во время контрольной Мария Ивановна перехватила записку Саше от Оли. Мария Ивановна очень хочет знать, что в записке, но, к сожалению, записка зашифрована. Мария Ивановна знает, что её ученики для шифровки заменяют каждую букву исходного сообщения на какую-то другую. Замена происходит таким образом, что одинаковые буквы всегда заменяются одной и той же буквой, а разные – разными.

Мария Ивановна подозревает, что записка – это ответы к контрольному тесту (ведь её длина случайно оказалась равной длине строки с правильными ответами). Однако она знает, что ответы Оли не обязательно полностью правильны. На каждый вопрос возможен один из K вариантов ответа. Естественно, Мария Ивановна знает правильные ответы.

Мария Ивановна решила расшифровать записку таким способом, чтобы максимизировать количество правильных ответов Оли. Однако, она очень занята, поэтому попросила Вас помочь ей в этом пустяковом деле.

Входные данные

В первой строке входного файла INPUT.TXT задана длина каждой из строк N (1 ≤ N ≤ 2 000 000) и K – количество возможных ответов на каждый вопрос (1 ≤ K ≤ 52). Ответы нумеруются в порядке abcde...xyzABCDE...XYZ. То есть, при K = 6 множество возможных ответов выглядит как abcdef, а при K = 30 – abcde...xyzABCD.

Во второй строке задана зашифрованная записка – строка, состоящая из строчных и заглавных английских букв.

В третьей строке заданы правильные ответы – строка той же длины, что и первая, состоящая из строчных и заглавных английских букв.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите единственное число – максимально возможное количество правильных ответов у Оли.

Во второй строке выведите расшифровку – строчку длины K, где по порядку для каждой буквы из шифра учеников указано, какому ответу она соответствует.

Если несколько расшифровок дают максимально возможное количество правильных ответов, выведите любую.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]