You are building the core delivery engine for a news publishing service. The service continuously receives news items, stores them, and — whenever a publish cycle is triggered — decides which stored news items should be delivered to which subscribers, based on each subscriber's interests and delivery limits. Implement a system that supports the following four operations. **`add_subscription(subscriber_id, topics, limit)`** - Registers a subscription for `subscriber_id`. - `topics` is a non-empty set of topic strings the subscriber is interested in. - `limit` is the maximum number of news items this subscriber may receive in a single `publish` cycle. - If the subscriber already has an active subscription, the old subscription is discarded and replaced, exactly as if `remove_subscription(subscriber_id)` had been called first: any undelivered backlog is dropped, and the new subscription only applies to news that arrives after this call. **`remove_subscription(subscriber_id)`** - Removes the subscriber's active subscription. Any news items that were queued for this subscriber but not yet delivered are discarded. - If the subscriber has no active subscription, this is a no-op. **`news_received(news_id, topic)`** - A news item with a unique identifier `news_id` and a single `topic` arrives and is stored. - Items arrive one at a time; the order of `news_received` calls defines the arrival order. **`publish()`** - Runs one delivery cycle and returns the delivery plan for this moment. - A stored news item is **eligible** for a subscriber if all of the following hold: 1. the item's `topic` is in the subscriber's interest set; 2. the item arrived **after** the subscriber's current subscription was created; 3. the item has not already been delivered to this subscriber in an earlier `publish` cycle. - Each subscriber receives their eligible items in arrival order (oldest first), up to at most `limit` items in this cycle. Eligible items beyond the limit are **not** dropped — they remain queued and are candidates in future `publish` cycles. - Returns a list of pairs `(subscriber_id, delivered_news_ids)` sorted by `subscriber_id` in ascending order, where `delivered_news_ids` is the ordered list of news ids delivered to that subscriber in this cycle. Subscribers who receive no items in this cycle are omitted. If no subscriber receives anything, return an empty list. ## Example ``` add_subscription(1, {"tech", "sports"}, 2) add_subscription(2, {"tech"}, 1) news_received(101, "tech") news_received(102, "sports") news_received(103, "tech") publish() # -> [(1, [101, 102]), (2, [101])] # Subscriber 1 has three eligible items (101, 102, 103) but limit 2, # so 103 stays queued. Subscriber 2 has two eligible items (101, 103) # but limit 1, so 103 stays queued. publish() # -> [(1, [103]), (2, [103])] add_subscription(3, {"sports"}, 5) publish() # -> [] # News 102 arrived before subscriber 3's subscription was created, # so it is not eligible for them; subscribers 1 and 2 have no # undelivered eligible items left. news_received(104, "finance") publish() # -> [] # No active subscriber is interested in "finance". ``` ## Constraints - Total number of operations across all four types is at most $10^5$. - `subscriber_id` and `news_id` are positive integers; every `news_id` is unique. - `topics` contains between 1 and 20 topic strings; topic strings are non-empty lowercase words. - $1 \le \text{limit} \le 100$. - `publish` may be called any number of times, including consecutively with no intervening news. - Aim for an implementation where each operation is efficient enough to handle the full operation stream well within typical time limits; avoid rescanning the entire news store for every subscriber on every `publish` cycle when a subscriber's undelivered backlog can be tracked incrementally.