courseera

from collections import defaultdict
import math
import os
import random
import re
import sys

"""
4,A,B,C
3,B,C,A
2,C,B,A
2,C,A,B


Count
A -> x
B -> b

1.) Creat a count Map [A] -> count
2.a) create a list and sort [(4,A), (2,B)]
2.b) creata a heap with these elements
    pick up top element
2.c) Scan the map entries get the max


A
A
B
B
C
C
D
D

2
[1,2,3,4] -> [1,3,4] ->

rep

1.) check if we have winner
    a.) if yes  then return the winner
    b.) No
        2.) delete min entry from all got0 step 1 with new input



"""

class BallotGroup:
    def __init__(self, votes: int, candidates: list[str]):
        self.votes = votes
        self.candidates = candidates

# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv

def pluralityWinner(ballots: list[BallotGroup]) -> str:
    countMap = defaultdict(int)
    candidate = None
    maxCount = 0
    for entry in ballots:
        count = entry.votes
        candidates = entry.candidates

        countMap[candidates[0]] += count

    for entry in countMap:
        key = entry
        val = countMap[key]
        if candidate == None:
            candidate = key
            maxCount = val
            continue

        if val > maxCount:
            candidate = key
            maxCount = val
        elif val == maxCount and key < candidate:
            candidate = key

    return candidate


def checkForWinner(votes) -> str:
    countMap = defaultdict(int)
    maxCount = 0
    candidate = None
    sz = len(votes)
    for entry in votes:
        countMap[entry[0]] += 1

    for key in countMap:
        if candidate == None:
            candidate = key
            maxCount = countMap[key]
            continue
        if maxCount < countMap[key]:
            candidate = key
            maxCount = countMap[key]



    if (maxCount > sz//2):
        return candidate

    else:
        return None


def getMinandTrim(votes: list[list[str]]) -> list[list[str]]:
    countMap = defaultdict(int)
    maxCount = len(votes) + 1
    candidate = None
    for entry in votes:
        countMap[entry[0]] += 1

    for key in countMap:
        if candidate == None:
            candidate = key
            maxCount = countMap[key]
            continue
        elif maxCount > countMap[key]:
            candidate = key
            maxCount = countMap[key]

        elif maxCount == countMap[key] and candidate < countMap[key]:
            candidate = key

    newVotes = []
    for entry in votes:
        temp = []
        for ele in entry:
            if ele != candidate:
                temp.append(ele)
        newVotes.append(temp)

    return newVotes







def rankedChoiceWinner(ballots: list[BallotGroup]) -> str:

    votes = []
    for entry in ballots:
        for _ in range(entry.votes):
            votes.append(entry.candidates)

    while True:
        winner = checkForWinner(votes)
        if winner != None:
            return winner
        votes = getMinandTrim(votes)

# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

def main():
    ballotsCount = int(input().strip().split(",")[0])

    ballots = list[BallotGroup]()
    for _ in range(ballotsCount):
        ballotLine = input().strip().split(",")
        ballots.append(BallotGroup(int(ballotLine[0]), ballotLine[1:]))

    with open(os.environ["OUTPUT_PATH"], "w") as outfile:
        outfile.write(f"pluralityWinner: {pluralityWinner(ballots)}\n")
        outfile.write(f"rankedChoiceWinner: {rankedChoiceWinner(ballots)}\n")

    # Disable unused import warnings for the default imports.
    _ = math, random, re, sys

if __name__ == "__main__":
    main()