Choosing a Team Name

Interview

Time limit2sMemory limit128 MB

Summary
Count letters L,O,V,E across a fixed name plus each candidate string, compute a formula mod 100, and print the candidate with the highest value, breaking ties by lexicographic order.
Level

Easy2 of 10

Topics
String, Implementation, Brute force
Solved
No attempts yet

Problem

Yeondoo is choosing a team name for a programming contest. Because she believes in superstition, she received a formula from Ihwan for calculating a team's chance of winning. She wants to use the formula to pick the candidate team name with the highest chance of winning.

The formula uses four variables: L, O, V, and E. Each variable is the number of times that letter appears after combining Yeondoo's English name with the team name.

  • L: the number of L characters in Yeondoo's English name and the team name
  • O: the number of O characters in Yeondoo's English name and the team name
  • V: the number of V characters in Yeondoo's English name and the team name
  • E: the number of E characters in Yeondoo's English name and the team name

Substitute these four values into the following expression to get the winning chance for that team name.

((L + O) × (L + V) × (L + E) × (O + V) × (O + E) × (V + E)) mod 100

Given Yeondoo's English name and N candidate team names, output the team name with the highest winning chance. If several candidates have the same highest chance, choose the lexicographically smallest team name.

Input

The first line contains Yeondoo's English name. The second line contains the number of candidate team names, N. Each of the next N lines contains one candidate team name.

Yeondoo's English name and every team name each have length between 1 and 20, inclusive, and consist only of uppercase English letters. N is a positive integer no greater than 50.

Output

Print the team name with the highest winning chance on the first line.

Examples6

  1. Example 1

    Input
    LOVE
3
JACOB
FRANK
DANO
    Expected output
    FRANK

  2. Example 2

    Input
    JANE
4
THOMAS
MICHAEL
INDY
LIU
    Expected output
    INDY

  3. Example 3

    Input
    LILLY
1
PIERRE
    Expected output
    PIERRE

  4. Example 4

    Input
    MERYLOV
5
JOHN
DAVE
STEVE
JOHN
DAVE
    Expected output
    DAVE

  5. Example 5

    Input
    LLOL
4
BVERON
CVERON
AVERON
DVERON
    Expected output
    AVERON

  6. Example 6

    Input
    VELYLEOCEVE
5
YVXHOVE
LCOKO
OGWSJVEVEDLE
WGFVSJEL
VLOLUVCBLLQVESWHEEKC
    Expected output
    VLOLUVCBLLQVESWHEEKC