## NBLTHIEF - 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 *L*_{0}
be the set of all suspects. Based on a clue '', a subset *L* of *L*_{0}
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 *L*_{0}, 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**.

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 *L*_{0} 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*^{*} 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

Added by: | Duc |

Date: | 2008-12-09 |

Time limit: | 0.179s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |

Resource: | ACM Kanpur 2004 |