Crystal's fortune predict system is successfully developed!

The predict system is a distributed system consists of computers. When it receives a predict request, each computer will generate one lowercase letter as its output. The final fortune predict result is determined by the concentration of all outputs.

Tired of getting bad predictions like , Ben decides to hack into the predict system and modify the predict result. He has already got the access permission of every computer in the predict system, so he can modify their output to any letter arbitrarily. 

As Ben is going to take part in ICPC Asia Regional Kunming Site 2077, he wants predictions like  or . He has found that the more times the substring  occurs in the concentration of all  outputs, the luckier he will get in the contest. But as the contest is coming soon, he only has time to modify at most outputs of the computers in the predict system.

As Ben is busy hacking into the system, could you tell him how to get the most  substrings after his modification?

The first line contains two integers  and  .

The second line contains a string of length , denoting the origin prediction. It is guaranteed that the string consists of lowercase English letters.

Output two lines. The first line contains a single integer, denotes the maximum number of  substring Bob can get, after his modification. The second line contains the final modified predict string. If there are multiple ways that results in the maximum number of  substring, print any.

9 2
arakbacca

3
acacbacca