Split stays

A holiday-rental site has n homes, numbered 0 .. n-1. free[i] lists the days (plain integers) on which home i can be booked; the list may be unsorted, may repeat days, and may be empty.

A guest wants to stay every night from day start to day end, both inclusive. When no single home is free for the whole trip, the site offers a split stay: the guest sleeps in home a for the first part of the trip and moves to a different home b for the rest. Formally, the trip can be booked as:

a single home i if i is free on every day start, start + 1, ..., end;
a split (a, b) with a != b if there is a switch day k with start <= k < end such that a is free on every day start .. k and b is free on every day k + 1 .. end. Neither home may be able to host the whole trip alone (if one of them could, the guest would just book it).

Write stay_options(free: list[list[int]], start: int, end: int) -> list[tuple[int, ...]] returning every option: each single home as a 1-tuple (i,) and each split as a 2-tuple (a, b). Order matters inside a split ((a, b) means a first). List each split once even if several switch days work, and return the whole list sorted with Python's normal tuple order.

free = [
    [1, 2, 3],        # home 0
    [3, 4, 5, 6],     # home 1
    [2, 3, 4],        # home 2
    [5, 3, 4, 1, 2],  # home 3
    [5, 6],           # home 4
]
stay_options(free, 2, 5)   # [(0, 1), (2, 1), (2, 4), (3,)]

Home 3 is free on days 2..5, so it is a single.
Counting from the first night, home 0 covers days 2..3 and home 2 covers 2..4. Counting back from the last night, home 1 covers 3..5 and home 4 covers 5..5.
(0, 1) works (switch day 2 or 3), (2, 1) works, and (2, 4) works with switch day 4. (0, 4) does not: day 4 is covered by neither.
Home 3 never appears in a split, because it can host the whole trip alone.

If start == end there is no switch day, so only singles are possible.

Constraints: n <= 10**4, at most 2 * 10**5 days across all lists, and start <= end with days up to 10**9, so the trip can be far longer than any home's list. The answer can hold many splits, but most homes are usually free at only one end of the trip (or neither); your time should depend on the input size plus the number of options returned, not on trying every pair of homes.