Contests  Virtual Contests  Problems  Submit  Runs Status  Rank List  Forum 


The costs are determined as follows: every inner node of the tree is marked with a sequence of length l, the cost of an edge of the tree is the number of positions at which the two sequences at the ends of the edge differ, the total cost is the sum of the costs at all edges. The sequence of a common ancestor of all sequences is then found at the root of the tree. An optimal common ancestor is a common ancestor with minimal total costs.
Input Specification
The input file contains several test cases. Each test case starts with two integers n and l, denoting the number of sequences at the leaves and their length, respectively. Input is terminated by n=l=0. Otherwise, 1≤n≤1024 and 1≤l≤1000. Then follow n words of length l over the amino acid alphabet. They represent the leaves of a complete binary tree, from left to right.
Output Specification
For each test case, output a line containing some optimal common ancestor and the minimal total costs.
Sample Input
4 3 AAG AAA GGA AGA 4 3 AAG AGA AAA GGA 4 3 AAG GGA AAA AGA 4 1 A R A R 2 1 W W 2 1 W Y 1 1 Q 0 0
Sample Output
AGA 3 AGA 4 AGA 4 R 2 W 0 Y 1 Q 0
Note: Special judge problem, you may get "Wrong Answer" when output in wrong format.