"""Stable partition: partition sequence into two groups preserving relative order within each.

stable_partition(items, pred) returns (truthy_list, falsy_list) where each
sublist preserves the original relative order of its members. Deterministic,
O(n) time, O(n) extra space. Empty input -> ([], []).
"""
from __future__ import annotations


def stable_partition(items, pred):
    if items is None:
        raise TypeError("items must not be None")
    if pred is None:
        raise TypeError("pred must not be None")
    yes = []
    no = []
    for x in items:
        (yes if pred(x) else no).append(x)
    return yes, no