The Nobel Thief
The Nobel Prize of Kabiguru Rabindranath Thagore was stolen from a museum of Viswa Bharati University in West Bengal. The Central Bureau of Investigation (CBI) has been assigned the job to investigate the crime and recover the prize. CBI has identified some suspects and linked each one of them to a distinct subset of a set of clues.
Let there be p suspects and q clues. Integers 1 to p identify suspects while q distinct letter-codes identify clues. The clues are of varying importance. The alphabetic order of letter-codes determines the priority order in the clues; letter-codes 'a' to 'z' vary from highest to lowest priority.
Let L0
be the set of all suspects. Based on a clue '
', a subset L of L0
may be split into two disjoint subsets
L+ 
and
L- .
The subset
L+ includes all elements of L that are linked to a
subset of clues containing '' and
L- includes all other
elements of L. Let n,
n+ , and
n-
denote respectively the total number of elements in L,
L+ and
L- . The discriminatory power of a clue '' to
discriminate suspects in L is defined by
= - (| n+ - n- |)
Let L* denote a set of disjoint subsets of L0, each subset containing two or more elements. The discriminatory power
of a clue '' to discriminate suspects in subsets contained in L is
defined to be the sum of all
's corresponding to each subset in L</em>.
CBI wants to select a set D of dominant clues so that the presence or absence of
some or all of these clues can identify each suspect uniquely. The selection is
to be done in stages.
Let L*
contain only L0 initially. At each stage of selection a clue
'
' with highest discriminatory power
is selected. Selecting the clue '' with highest priority breaks tie, if
any. After a selection of '' each L in L* is split into
disjoint subsets
L+ 
and '
L- ' all resulting
subsets with less than two elements are dropped from L. The process of
selection continues until L</em> becomes empty. All the clues thus selected form
the set of dominant clues D.
You are required to write a program to find the set of dominant clues D.
Input
Input may contain multiple test cases. For each test case input is given in one line. It contains an integer k representing the case number and a certain number of strings of clues. The i-th string represents the subset of clues to which the i-th suspect is linked. A space separates two consecutive fields in input.
Input terminates with an input 0 for the case number k.
Output
For each test case, present output in one line. The line contains the case number k and a string of letters. The letters in the string correspond to the clues in D
and appear in the order of their selection.
Sample Input
1 cbx cpxb bc brc 2 bac adce cbd d 0
Sample Output
1 xpr 2 ab
Kanpur-Kolkata 2004-2005