from typing import List
from typing import Tuple


def consolidate_spans(spans: List[Tuple[int, int]], caption: str, rec=True):
    """Accepts a list of spans and the the corresponding caption.
    Returns a cleaned list of spans where:
        - Overlapping spans are merged
        - It is guaranteed that spans start and end on a word
    """
    sorted_spans = sorted(spans)
    cur_end = -1
    cur_beg = None
    final_spans: List[Tuple[int, int]] = []
    for s in sorted_spans:
        if s[0] >= cur_end:
            if cur_beg is not None:
                final_spans.append((cur_beg, cur_end))
            cur_beg = s[0]
        cur_end = max(cur_end, s[1])

    if cur_beg is not None:
        final_spans.append((cur_beg, cur_end))

    # Now clean the begining/end
    clean_spans: List[Tuple[int, int]] = []
    for s in final_spans:
        beg, end = s
        end = min(end, len(caption))
        while beg < len(caption) and not caption[beg].isalnum():
            beg += 1
        while end > 0 and not caption[end - 1].isalnum():
            end -= 1
        # Try to get hyphenated words
        if end < len(caption) and caption[end] == "-":
            # print("trigg")
            next_space = caption.find(" ", end)
            if next_space == -1:
                end = len(caption)
            else:
                end = next_space + 1
        if beg > 0 and caption[beg - 1] == "-":
            prev_space = caption.rfind(" ", 0, beg)
            if prev_space == -1:
                beg = 0
            else:
                beg = prev_space + 1
        if 0 <= beg < end <= len(caption):
            clean_spans.append((beg, end))
    if rec:
        return consolidate_spans(clean_spans, caption, False)
    return clean_spans