有一天,玛丽亚·伊万诺夫娜 (Maria Ivanovna) 发现了萨莎 (Sasha) 的一张纸,上面有一条献给奥莉亚 (Olya) 的信息。玛丽亚·伊万诺芙娜想知道消息中包含什么内容,但不幸的是该消息已被加密。玛丽亚·伊万诺夫娜知道,她的学生通常通过用另一个字母替换原始消息中的每个字母来加密他们的消息。替换的工作方式是相同的字母总是被某个固定的字母替换,不同的字母总是被不同的字母替换。
Maria Ivanovna 认为该消息包含期末考试的答案(因为其长度等于期末考试问题的数量)。另一方面她知道萨莎的回答不一定是正确的。每个问题有 K 个可能的答案。当然,玛丽亚·伊万诺芙娜知道正确答案。
玛丽亚·伊万诺夫娜 (Maria Ivanovna) 决定以萨莎正确答案数量尽可能多的方式破译消息。她现在很忙,所以你的任务就是帮助她。
输入
第一行包含字符串 N (1 ≤ N ≤ 2 000 000) 的长度和整数 K - 每个问题的可能答案数量 (1 ≤ K ≤ 52)。问题的答案按顺序表示为拉丁字母 abcde...xyzABCDE...XYZ。例如,对于 K = 6,可能的答案为 abcdef,对于 K = 30,可能的答案为 abcde...xyzABCD。
第二行包含由拉丁字母组成的加密消息字符串。
第三行包含由拉丁字母组成的正确答案字符串。
输出
在第一行输出正确 Sasha 答案的最大可能数量。
在第二行中,输出密码规则作为长度为 K 的字符串,其中对于学生密码中的每个字母(如上所述从“a”开始),指定了它对应的答案。
如果有多种方法可以产生最大答案,则输出其中任何一种。
示例
输入 #1
10 2 aaabbbaaab bbbbabbbbb
输出 #1
7 ba
输入 #2
10 2 aaaaaaabbb bbbbaaabbb
输出 #2
6 ab
输入 #3
9 4 dacbdacbd acbdacbda
输出 #3
9 cdba