Merge K Timestamp-Sorted Price Feeds into a Running Absolute Price

You are given K data feeds of price events. Each event is a pair [timestamp, delta]: the time at which the event occurred and the change in price it carries. Within each feed, events are already listed in non-decreasing timestamp order. A feed's index is its position in the input list, from 0 to K - 1.

Process the events from all feeds as one chronological stream. The absolute price starts at 0, and each event adds its delta to it. Return the absolute price recorded after each event, in processing order.

Function Signature

def running_prices(feeds: list[list[list[int]]]) -> list[int]:

Rules

• Processing order. An event with a smaller timestamp is processed before an event with a larger one. When two events share a timestamp and come from different feeds, the event from the feed with the smaller index is processed first. When two events share a timestamp and come from the same feed, they are processed in the order they appear in that feed. Equivalently, events are processed in ascending order of the key (timestamp, feed index, position within its feed).
• Running price. The price starts at 0. Processing an event sets price = price + delta, and the new price is appended to the output, so the output holds exactly one value per event.
• Negative values. Deltas may be negative, and the running price may drop below zero. It is never clamped.
• Empty feeds. A feed may contain no events, in which case it contributes nothing. If there are no events at all, including when feeds itself is empty, return an empty list.

Constraints

• 0 <= K = len(feeds) <= 10000
• 0 <= N <= 100000, where N is the total number of events across all feeds
• Every event is a list of exactly two integers, [timestamp, delta].
• 0 <= timestamp <= 1000000000
• -1000000 <= delta <= 1000000
• Within each feed, timestamps are non-decreasing, so equal timestamps may repeat inside one feed. Different feeds have no ordering relationship with each other.
• Every running price lies between -100000000000 and 100000000000 inclusive. This exceeds the 32-bit signed integer range (2^31 - 1), so use 64-bit integers in fixed-width languages.
• The output is a list of length N, and it is uniquely determined by the input.

Examples

Example 1

• Input: feeds = [[[1, 5], [4, -2]], [[2, 3], [3, -1]]]
• Output: [5, 8, 7, 5]
• Explanation: The processing order is [1, 5] from feed 0, [2, 3] from feed 1, [3, -1] from feed 1, then [4, -2] from feed 0. Starting from 0, the price becomes 5, 8, 7 and finally 5.

Example 2

• Input: feeds = [[[2, -4], [2, 1]], [], [[1, 10], [2, 7]]]
• Output: [10, 6, 7, 14]
• Explanation: Feed 1 is empty. The only event at timestamp 1 is [1, 10] from feed 2, so it is processed first and the price becomes 10. Three events share timestamp 2. The two from feed 0 come first, in their order within that feed (-4 and then 1, giving 6 and then 7), followed by [2, 7] from feed 2, giving 14.

Example 3

• Input: feeds = [[[3, -2]], [[1, -5], [3, 4]]]
• Output: [-5, -7, -3]
• Explanation: [1, -5] from feed 1 is processed first, so the price becomes -5. At timestamp 3, the event from feed 0 precedes the event from feed 1, so the price moves to -7 and then to -3. The price stays negative throughout, which is allowed.