class FoodRatings:

    def __init__(self, foods, cuisines, ratings):
        self.foods = foods
        self.cuisines = cuisines
        self.ratings = ratings

    def changeRating(self, food, newRating):
        for index, current_food in enumerate(self.foods):
            if current_food == food:
                self.ratings[index] = newRating
                break

    def highestRated(self, cuisine):
        highest_rating = -1
        highest_rated_food_for_cuisine = None

        # Iterate through all food items in the system
        for index, current_food in enumerate(self.foods):

            # Check if the current food belongs to the target cuisine
            if self.cuisines[index] == cuisine:

                # Compare current food's rating to the highest rating seen so far
                if self.ratings[index] > highest_rating:
                    highest_rating = self.ratings[index]
                    highest_rated_food_for_cuisine = current_food
                elif self.ratings[index] == highest_rating:
                    #Break Ties by using lexicographical order if the ratings match
                    if current_food < highest_rated_food_for_cuisine:
                        highest_rated_food_for_cuisine = current_food

        return highest_rated_food_for_cuisine

class FoodRatingSystem:

    def __init__(self, foods, cuisines, ratings):
        self.food_to_cuisine = {}
        self.food_to_rating = {}
        self.cuisine_to_foods = {}
        for i in range(len(foods)):
            food = foods[i]
            cuisine = cuisines[i]
            rating = ratings[i]
            self.food_to_cuisine[food] = cuisine
            self.food_to_rating[food] = rating

            # Use a sorted list to track top foods efficiently
            if cuisine not in self.cuisine_to_foods:
                self.cuisine_to_foods[cuisine] = []
            self.cuisine_to_foods[cuisine].append((rating, food))
        for cuisine in self.cuisine_to_foods:
            self.cuisine_to_foods[cuisine].sort(key=lambda x: (-x[0], x[1]))

    def changeRating(self, food, new_rating):
        self.food_to_rating[food] = new_rating
        cuisine = self.food_to_cuisine[food]

        # Update rating and sort the list of foods
        foods_in_cuisine = self.cuisine_to_foods[cuisine]
        for i in range(len(foods_in_cuisine)):
            if foods_in_cuisine[i][1] == food:
                foods_in_cuisine[i] = (new_rating, food)
                break
        self.cuisine_to_foods[cuisine].sort(key=lambda x: (-x[0], x[1]))

    def highestRated(self, cuisine):
        # Retrieve highest rated food directly from sorted list
        return self.cuisine_to_foods[cuisine][0][1]