Implement the following in Python 3 using only the standard ...

Prompt

Implement the following in Python 3 using only the standard library. Output exactly one fenced ```python code block and nothing else: no explanation, no text before or after the block, no tests, no `print` calls, no `if __name__ == "__main__"` block. Write a class `Bookings` for a meeting-room system. class Bookings: def __init__(self, capacity: int): ... def book(self, start: int, end: int) -> bool: ... def cancel(self, start: int, end: int) -> bool: ... def max_overlap(self, start: int, end: int) -> int: ... Rules: 1. Intervals are half-open: [start, end). [1,3) and [3,5) do NOT overlap. 2. `book` adds the interval and returns True only if, after adding it, no instant is covered by more than `capacity` bookings. Otherwise it changes nothing and returns False. 3. Identical intervals may be booked multiple times (each is a separate booking). `cancel` removes exactly ONE matching booking and returns True; it returns False if none exists. 4. `max_overlap(start, end)` returns the highest number of bookings covering any single instant inside [start, end), or 0 if the window is empty or nothing overlaps it. 5. `book` and `max_overlap` raise `ValueError` if `start >= end`. `book` also raises `ValueError` if `capacity < 1`, checked at construction (in `__init__`). `cancel` with `start >= end` returns False and does not raise. 6. Integer coordinates may be as large as 10**18 and there may be up to 10**5 operations, so no per-unit-of-time arrays or loops over the coordinate range. 7. Every public method must run in O(log n) or O(n) at worst per call, never O(n^2) per call. Do not use third-party libraries (e.g. sortedcontainers). Examples (must hold): b = Bookings(2) b.book(10, 20) # True b.book(15, 25) # True b.book(17, 18) # False (would make 3 overlap at 17) b.book(20, 30) # True (touches [10,20) only at the boundary) b.max_overlap(0, 100) # 2 b.max_overlap(25, 30) # 1 b.max_overlap(30, 40) # 0 b.cancel(15, 25) # True b.cancel(15, 25) # False b.book(17, 18) # True