## Multi-Level Warehouse Storage with Weighted Retrieval You are building the in-memory engine for an automated warehouse. The warehouse is a stack of horizontal **levels** (shelves), indexed from `0` at the **top** to `num_levels - 1` at the **bottom**. Each level can hold at most `capacity` items. Every item has an integer `weight` and is placed at an integer `timestamp` (a logical clock). An item **expires** once `ttl` time units have elapsed since it was stored: an item stored at time `t` is valid for a query at time `q` while `q < t + ttl`, and is expired (and must never be returned) once `q >= t + ttl`. Implement a class `Storage` with the methods below. ### Methods **`__init__(self, num_levels, capacity, ttl)`** Initialize an empty warehouse with `num_levels` levels, each able to hold `capacity` items, and the given item `ttl`. Assume `num_levels >= 1`, `capacity >= 1`, and `ttl >= 1`. **`store(self, item_id, weight, timestamp) -> int`** Place one item into the warehouse. - The item must be placed on the **topmost** level (smallest index) that currently has at least one free slot, counting only items that have not yet expired at this `timestamp`. - Return the index of the level on which the item was placed. - If every level is full of non-expired items, do not store the item and return `-1`. - You may assume each `item_id` passed to `store` is unique across the lifetime of the object, and that `timestamp` values are non-decreasing across successive calls. **`retrieve(self, timestamp) -> Optional[int]`** Select and remove exactly one item, returning its `item_id`. Apply these rules **in order**: 1. **Expire first.** On every level, remove all items that are expired at this `timestamp` (`timestamp >= stored_time + ttl`). Their slots become free and they can never be retrieved. 2. **Scan top to bottom.** Consider levels from index `0` downward. A level is a **candidate** only if, after step 1, it is still at least half full — that is, the number of valid items currently on it is at least `ceil(capacity / 2)`. 3. **Pick within the first candidate level.** From the topmost candidate level, choose the item with the **greatest `weight`**; break ties by the **smallest `item_id`**. Remove it from that level and return its `item_id`. 4. If no level qualifies, return `None`. ### Constraints & Notes - Levels are the primary ordering for retrieval (topmost eligible level wins); weight is only the selector **within** the chosen level. - "Half full" uses the level's `capacity`, not how many items it has ever held: a level with `c` valid items qualifies iff `c >= ceil(capacity / 2)`. - All `weight`, `timestamp`, and `ttl` values are non-negative integers; `weight` may repeat across items. - Expiration is evaluated lazily at the start of each `retrieve` (and when counting free slots in `store`); you are not required to evict expired items at any other time. ### Example ```text s = Storage(num_levels=2, capacity=2, ttl=10) s.store(1, weight=5, timestamp=0) # -> 0 (level 0 has space) s.store(2, weight=8, timestamp=0) # -> 0 (level 0 still has space) s.store(3, weight=3, timestamp=1) # -> 1 (level 0 now full) s.retrieve(timestamp=2) # -> 2 # No expirations (ttl=10). Level 0 has 2 valid items; ceil(2/2)=1, so it is a # candidate and is topmost. Highest weight on level 0 is item 2 (weight 8). s.retrieve(timestamp=2) # -> 1 # Level 0 now has 1 valid item; 1 >= ceil(2/2)=1, still a candidate. # Only item 1 remains there, so it is returned. s.retrieve(timestamp=2) # -> 3 # Level 0 has 0 items (0 < 1), not a candidate. Level 1 has 1 item # (1 >= 1), so item 3 is returned. s.retrieve(timestamp=2) # -> None (warehouse empty) ``` An expiry example: with `ttl=10`, an item stored at `timestamp=0` is still valid at `retrieve(timestamp=9)` but is treated as expired (removed, never returned) at `retrieve(timestamp=10)`.