DNA

A DNA string can be represented with the four nucleotide letters A, C, G, and T. For two DNA strings of the same length, their Hamming Distance is the number of positions where the two characters are different.

You are given N DNA strings s_1, s_2, ..., s_N, each of length M. Choose one DNA string S of length M so that the sum of the Hamming Distances between S and all given strings is as small as possible. In other words, minimize d(S, s_1) + d(S, s_2) + ... + d(S, s_N). If several strings are possible, choose the lexicographically smallest one.

The first line contains the number of DNA strings N and the length M of each string. Each of the next N lines contains one DNA string of length M.

N is between 1 and 1,000 inclusive, and M is between 1 and 50 inclusive. Each DNA string consists only of the characters A, C, G, and T.

Print a DNA string whose total Hamming Distance is minimum on the first line. If several such strings exist, print the lexicographically smallest one.

Print the minimum total Hamming Distance on the second line.