Which Chapter Is This Bookmark In?

An audiobook app stores each book as a list of chapters (title, seconds) and each listener's bookmarks as a number of seconds from the start of the book. A first version finds the chapter of a bookmark like this:

def locate(chapters, times):
    out = []
    for t in times:
        start, found = 0, None
        for title, length in chapters:
            if start <= t < start + length:
                found = (title, t - start)
                break
            start += length
        out.append(found)
    return out

It is correct, but for a lecture series with 10**5 chapters and 10**5 bookmarks it takes minutes. Write a locate(chapters, times) that returns the same results fast: for each bookmark t, the pair (title, seconds into that chapter), or None if t is at or past the end of the book.

A bookmark exactly at the start of a chapter belongs to that chapter, at offset 0.

Examples

Input:  locate([("Intro", 90), ("Storm", 300), ("Harbour", 240)], [0, 89, 90, 389, 390, 629, 630])
Output: [("Intro", 0), ("Intro", 89), ("Storm", 0), ("Storm", 299), ("Harbour", 0), ("Harbour", 239), None]

Constraints

• 0 <= len(chapters), len(times) <= 10**5; every chapter length is a positive whole number; 0 <= t <= 10**12.
• times is in no particular order, and the result follows the order of times.

Goals

• Replace a hand-written running total with `itertools.accumulate`
• Replace a linear scan over sorted boundaries with `bisect`
• Get the boundary cases (exactly at a chapter start, past the end) right