Under construction

Still being built. Things may change

Recount

Interview

Time limit3sMemory limit1024 MB

Summary
Given one candidate name per vote, find the candidate with strictly more votes than any other, or print Runoff! if no candidate leads outright.
Level

Easy3 of 10

Topics
Hash map, String
Solved
No attempts yet

Problem

The recent school board elections were hotly contested. One proposal swaps the start times for elementary and high school students. A controversial new dress code bans athletic clothes in school. Another proposal raises real-estate taxes to pay for a new football practice facility. The list goes on. It is now hours after the polls closed, and no winner has emerged!

In desperation, the election officials turn to you and ask you to write a program to count the votes!

Input

The input consists of a single test case, which is a list of votes cast. Each line contains the name of a candidate who received a vote. A name may consist of multiple words separated by spaces. Words contain letters or hyphens, but no other punctuation characters. There are at least 2 votes. The list ends with a single line containing the characters ***. This line is not counted. There can be up to 100,000100,000 valid votes.

Output

If a candidate obtained a simple or absolute majority of all votes cast (that is, more than any other candidate), output the name of this candidate. If no candidate obtained a simple majority, output "Runoff!" (don't forget the exclamation mark!).

Examples2

  1. Example 1

    Input
    Penny Franklin
Marti Graham
Connie Froggatt
Joseph Ivers
Connie Froggatt
Penny Franklin
Connie Froggatt
Bruce Stanger
Connie Froggatt
Barbara Skinner
Barbara Skinner
***
    Expected output
    Connie Froggatt

  2. Example 2

    Input
    Penny Franklin
Connie Froggatt
Barbara Skinner
Connie Froggatt
Jose Antonio Gomez-Iglesias
Connie Froggatt
Bruce Stanger
Barbara Skinner
Barbara Skinner
***
    Expected output
    Runoff!