Weighted Scores at the Bake-Off

At a village bake-off every cake is described by a vector of marks, for example [taste, look, originality, minutes over time]. The judges agree on one weight per mark: how many points each unit of that mark is worth. A negative weight is a penalty (every minute over time costs points).

The score of a cake is the sum, over all positions, of weight times mark. Write rank_cakes(weights, cakes) that returns the indices of the cakes from the highest score to the lowest. Cakes with equal scores keep their original order (smaller index first).

Examples

Input:  weights = [5, 2, 3, -1]
        cakes = [[8, 6, 4, 0], [9, 5, 2, 10], [7, 9, 6, 2]]
Output: [2, 0, 1]
Explanation: the scores are 5·8 + 2·6 + 3·4 - 0 = 64, 45 + 10 + 6 - 10 = 51 and 35 + 18 + 18 - 2 = 69.

Input:  weights = [1, 1]
        cakes = [[2, 3], [4, 1], [0, 5]]
Output: [0, 1, 2]
Explanation: all three cakes score 5, so they stay in index order.

Constraints

• 1 <= len(cakes) <= 10**4, every cake has the same length as weights, between 1 and 20
• weights and marks are whole numbers between -1000 and 1000

Goals

• Compute a dot product as a weighted sum of features
• Let a negative weight act as a penalty
• Rank entries by score with a clear tie rule