Задача №111556. Расшифровка
Недавно на уроке во время контрольной Мария Ивановна перехватила записку Саше от Оли. Мария Ивановна очень хочет знать, что в записке, но, к сожалению, записка зашифрована. Мария Ивановна знает, что её ученики для шифровки заменяют каждую букву исходного сообщения на какую-то другую. Замена происходит таким образом, что одинаковые буквы всегда заменяются одной и той же буквой, а разные — разными.
Мария Ивановна подозревает, что записка — это ответы к контрольному тесту (ведь её длина случайно оказалась равной длине строки с правильными ответами). Однако она знает, что ответы Оли не обязательно полностью правильны. На каждый вопрос возможен один из K вариантов ответа. Естественно, Мария Ивановна знает правильные ответы.
Мария Ивановна решила расшифровать записку таким способом, чтобы максимизировать количество правильных ответов Оли. Однако, она очень занята, поэтому попросила Вас помочь ей в этом пустяковом деле.
В первой строке задана длина каждой из строк N (1 ≤ N ≤ 2 000 000) и K — количество возможных ответов на каждый вопрос (1 ≤ K ≤ 52). Ответы нумеруются в порядке abcde...xyzABCDE...XYZ. То есть, при K = 6 возможные ответы выглядят как abcdef, а при K = 30 "— abcde...xyzABCD.
Во второй строке задана зашифрованная записка — строка, состоящая из строчных и заглавных латинских букв.
В третьей строке заданы правильные ответы — строка той же длины, что и первая, состоящая из строчных и заглавных латинских букв.
В первой строке выведите единственное число — максимально возможное количество правильных ответов у Оли.
Во второй строке выведите расшифровку — строчку длины K, где по порядку для каждой буквы из шифра учеников указано, какому ответу она соответствует.
Если несколько расшифровок дают правильный ответ, выведите любую.
Тесты к этой задаче состоят из четырех групп.
- Тесты 1-3. Тесты из условия, оцениваются в ноль баллов.
- Тесты 4-15. В тестах этой группы K = 2. Решение оценивается в 15 баллов.
- Тесты 16-40. В тестах этой группы K ≤ 9. Решение оценивается в 15 баллов.
- Тесты 41-75. В тестах этой группы K ≤ 26. Решение оценивается в 30 баллов.
- Тесты 76-115. Дополнительные ограничения отсутствуют. Решение будет тестироваться на тестах этой группы только в случае прохождения всех предыдущих групп. Группа оценивается в 40 баллов.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы. Тестирование на очередной группе начинается только после полного прохождения предыдущей.
10 2 aaabbbaaab bbbbabbbbb
7 ba
10 2 aaaaaaabbb bbbbaaabbb
6 ab
9 4 dacbdacbd acbdacbda
9 cdba