DNA

Interview

Time limit2sMemory limit128 MB

Summary

Given N DNA strings of length M, construct the string minimizing total Hamming distance to all, breaking ties lexicographically, and output that distance.

Level: Easy3 of 10
Topics: String, Greedy, Implementation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples3

Example 1

Input

5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

Expected output

TAAGATAC
7

Example 2

Input

4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA

Expected output

ACGTACGTAA
6

Example 3

Input

6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA

Expected output

AAGTTACCAA
12