Library display shelves over time

A library has display shelves that each feature one book at a time. Staff log every change, and later someone asks what was on a shelf at a given moment, or which books a shelf featured during a period.

Implement class ShelfLog:

• put(shelf: str, book: str, t: int): from time t on, shelf features book (replacing whatever it had).
• clear(shelf: str, t: int): from time t on, shelf is empty.
• at(shelf: str, t: int) -> str | None: the book featured at time t, meaning the one from the latest put/clear on that shelf at or before t. Return None if that latest change was a clear, or if the shelf had no change yet (or was never mentioned).
• featured(shelf: str, t1: int, t2: int) -> list[str]: every book the shelf featured at any moment in [t1, t2] (with t1 <= t2), in the order they were put up. That's the book featured at t1 (if any), followed by the books of every put with t1 < time <= t2. A book put up twice appears twice.

Every put/clear call uses a time strictly greater than all earlier put/clear calls. Queries can come at any point and ask about any time, including negative ones or times before a shelf's first change.

log = ShelfLog()
log.put("window", "Dune", 10)
log.put("window", "Emma", 20)
log.clear("window", 30)
log.put("window", "Dune", 40)
log.at("window", 25)               # "Emma"
log.at("window", 35)               # None     (cleared at 30)
log.at("window", 5)                # None     (nothing yet)
log.featured("window", 15, 40)     # ["Dune", "Emma", "Dune"]
log.featured("window", 30, 39)     # []       (empty the whole time)
log.featured("lobby", 0, 100)      # []

The tests log 100,000 changes and make 100,000 queries, so scanning a shelf's whole history per query is too slow: aim for O(log n) per at (plus the size of the answer for featured).