ICS 4U – PROGRAM 03
A NEW ELECTORAL SYSTEM

Problem Description
The discussion to change the existing electoral system in Canada seems to be gaining momentum. In the very least, it was an important issue during recent elections.

One proposed system is to have each voter rank each candidate with numbers 1 through n where n is the total number of candidates. The number 1 would represent the voter's favourite choice, the number 2 would represent the voter's 2^nd choice and so on…

When tabulating the votes, we consider only the number 1s. We then eliminate the candidate with the least votes. The ballots with this candidate at number 1 will now have a different candidate at their number 1 spot. We again consider the number 1^st and eliminate the weakest candidate. Again, the ballots are updated. We continue this process until we are down to two candidates. This winning candidate is then declared the winner.

Note that when doing elimination, there may be ties for the worst candidate. We then compare who of the tied worst candidates is the worst amongst 2^nd place votes. Any tied would again be compared at the 3^rd place vote spot. And so on. If completely equal, then eliminated the first one alphabetically. Note that this is not a perfect system but it will usually work fine.

Input Specification

The first line will contain the number C (2 ≤ C ≤ 26) which is the number of different candidates running in the election.

The next line will contain the number V (1 ≤ C ≤ 100) which is the number of voters that will votes in the election.

Each of the next V lines will contain a series of letters (each representing a candidate). Each candidate will be represented each line. A candidate will be represented by a letter such as A, B, C, …. The first candidate listed is considered the voter's 1^st choice, the 2^nd is the voter's 2^nd choice, and so on…

Output Specification

After the election input has been provided, each of the next rounds with elimination details should be outputted.

Sample Input 1

3

5

ACB

BAC

BCA

ACB

CBA

Output for Sample Input 1
Elimination of C

AB

BA

BA

AB

BA

Two candidates remain.

B wins, A loses

Sample Input 2

5

6

ADEBC

BADCE

EDCBA

DABCE

EABCD

AEBDC

Output for Sample Input 2
Elimination of C

ADEB

BADE

EDBA

DABE

EABD

AEBD

Elimination of B (Had to compare 2^nd place votes to compare B and E)

ADE

ADE

EDA

DAE

EAD

AED

Elimination of D

AE

AE

EA

AE

EA

AE

Two candidates remain.

A wins, E loses.