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 ```python 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.