// CS100J, Spring 2002
// Assignment 4 Sample Solution -- Hare Voting
// Name: Tim Teitelbaum 
public class HareVoting {
    final static char base = 'A';      // name of smallest candidate
    final static int maxvoters = 100;  // max # of voters
    final static int Ncandidates = 26; // # of candidates
	final static int infinity = Ncandidates + 1;

    public static void main(String[] args) {
        TokenReader in = new TokenReader(System.in);
        
		// Initially, let ballot[0..Nvoters] be all ballots in input.
		// Subsequently, ballot[0..Nvoters] is all ballots in input 
    	// that have not been discarded. A ballot is discarded when 
    	// all of its preferences are eliminated.  
        String[] ballot = new String[maxvoters]; 
        int Nvoters = 0; 
        String s = in.readString();
        while(!s.equals("end")) 
        {
            ballot[Nvoters] = s; Nvoters++;
            s = in.readString();
        }

		// Repeatedly eliminte least popular first choice candidate
        // until a majority of remaining ballots agree on a first choice.
        boolean noMajority = true; // true if no candidate has a majority yet.
        while (noMajority) 
        {
        	// Let freq[i] be the number of first-choice votes  
        	// for candidate 'A'+i.
            int[] freq = new int[Ncandidates];
            for (int i=0; i<Nvoters; i++)
               	  freq[ballot[i].charAt(0) - base]++;
            
            // Let leader (respectively, pariah) be the index of the most
            //  (respectively, least) popular candidate receiving 1 or more votes.
            int pariah=-1; // least popular in the round.
       		int leader=-1; // most popular in the round.
       		int maxVotes = -infinity;
       		int minVotes = +infinity;
            for (int i=0; i<Ncandidates; i++) 
            	{
            	   	if (freq[i] > maxVotes) 
            	   		{leader = i; maxVotes = freq[i];}
                	if (freq[i] < minVotes && freq[i] > 0) 
                		{pariah = i; minVotes = freq[i];}
           		 }
            
            noMajority = (freq[leader] <= Nvoters/2);
            
            if ( noMajority ) 
            {
           		// Delete pariah from all ballots,
           		// and eliminate any empty ballot so created.
            	for (int i=0; i<Nvoters; i++) {
            		int bLength = ballot[i].length();
            		
            		// Let j be index in ballot[i] of the vote for pariah,
            		// if such a vote exists; otherwise let j be bLength
            		int j = 0; 
                	while (	j < bLength && ballot[i].charAt(j) - base != pariah)
                		j++;
                	
                	// If j != bLength, delete jth vote from ballot[i],
                	// and discard ballot[i] if it has no further choices.
                	if (j != bLength) {
                		ballot[i] = ballot[i].substring(0,j) 
                    	+ ballot[i].substring(j+1,ballot[i].length());
                    	if (ballot[i].length()==0){
                    		Nvoters--;
                    		ballot[i]=ballot[Nvoters];
                    		}
                    	}
           			}
           	}
           	else System.out.println("\n\nWinner is " + (char)(leader + base));
        }
    }
}