Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Phylogenetic Trees Inherited
Time Limit: 3000MSMemory Limit: 65536K
Total Submissions: 530Accepted: 326Special Judge

Description

Among other things, Computational Molecular Biology deals with processing genetic sequences. Considering the evolutionary relationship of two sequences, we can say that they are closely related if they do not differ very much. We might represent the relationship by a tree, putting sequences from ancestors above sequences from their descendants. Such trees are called phylogenetic trees.
Whereas one task of phylogenetics is to infer a tree from given sequences, we'll simplify things a bit and provide a tree structure - this will be a complete binary tree. You'll be given the n leaves of the tree. Sure you know, n is always a power of 2. Each leaf is a sequence of amino acids (designated by the one-character-codes you can see in the figure). All sequences will be of equal length l. Your task is to derive the sequence of a common ancestor with minimal costs.
Amino Acid
AlanineAlaA
ArginineArgR
AsparagineAsnN
Aspartic AcidAspD
CysteineCysC
GlutamineGlnQ
Glutamic AcidGluE
GlycineGlyG
HistidineHisH
IsoleucineIleI
Amino Acid
LeucineLeuL
LysineLysK
MethionineMetM
PhenylalaninePheF
ProlineProP
SerineSerS
ThreonineThrT
TryptophanTrpW
TyrosineTyrY
ValineValV

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

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

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

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator