class FoodRatings:
    def __init__(self, foods: list[str], cuisines: list[str], ratings: list[int]):
        # Create a single master list to hold all food details for straightforward iteration.
        self.food_master_list = []
        for index in range(len(foods)):
            food_name = foods[index]
            cuisine_type = cuisines[index]
            initial_rating = ratings[index]
            self.food_master_list.append([food_name, cuisine_type, initial_rating])

    def changeRating(self, food: str, newRating: int) -> None:
        # We must search the entire list to find the matching food by its name to update the rating.
        for food_record in self.food_master_list:
            if food_record[0] == food:
                food_record[2] = newRating
                return

    def highestRated(self, cuisine: str) -> str:
        # Initialize a variable to keep track of the best food found so far for the target cuisine.
        current_best_food_for_cuisine = None

        for food_record in self.food_master_list:
            food_name = food_record[0]
            food_cuisine = food_record[1]
            food_rating = food_record[2]

            if food_cuisine == cuisine:
                # A food becomes the new winner if its rating is higher, or if tied, its name is smaller.
                if current_best_food_for_cuisine is None or \
                   food_rating > current_best_food_for_cuisine[2] or \
                   (food_rating == current_best_food_for_cuisine[2] and food_name < current_best_food_for_cuisine[0]):
                    current_best_food_for_cuisine = food_record
        
        return current_best_food_for_cuisine[0]

class FoodRatings:
    def __init__(self, foods: list[str], cuisines: list[str], ratings: list[int]):
        # A map for O(1) access to a food's current rating and cuisine.
        self.food_info = {}

        self.cuisine_leaderboards = collections.defaultdict(list)

        for index in range(len(foods)):
            food_name = foods[index]
            cuisine_name = cuisines[index]
            initial_rating = ratings[index]
            
            self.food_info[food_name] = [initial_rating, cuisine_name]
            # Storing ratings as negative allows a min-heap to function as a max-heap.
            heapq.heappush(self.cuisine_leaderboards[cuisine_name], (-initial_rating, food_name))

    def changeRating(self, food_to_update: str, new_rating: int) -> None:
        original_cuisine = self.food_info[food_to_update][1]
        self.food_info[food_to_update][0] = new_rating
        
        # This lazy-add avoids a costly search-and-remove from the heap for the old rating.
        heapq.heappush(self.cuisine_leaderboards[original_cuisine], (-new_rating, food_to_update))

    def highestRated(self, cuisine_to_query: str) -> str:
        leaderboard_for_cuisine = self.cuisine_leaderboards[cuisine_to_query]
        
        # Stale ratings might be at the top, so we must find the first valid one.
        while -leaderboard_for_cuisine[0][0] != self.food_info[leaderboard_for_cuisine[0][1]][0]:
            heapq.heappop(leaderboard_for_cuisine)
        
        return leaderboard_for_cuisine[0][1]