def zip_pairs(xs, ys, key=lambda x: x):
    """Generate pairs that match a cmp function"""
    xs = list(reversed(sorted(xs, key=key)))
    ys = list(reversed(sorted(ys, key=key)))
    while xs or ys:
        if xs and not ys:
            yield xs.pop(), None
        elif ys and not xs:
            yield None, ys.pop()
        elif key(xs[-1]) == key(ys[-1]):
            yield xs.pop(), ys.pop()
        elif key(xs[-1]) < key(ys[-1]):
            yield xs.pop(), None
        else:
            yield None, ys.pop()
