class PartialLinearMapping:
    range_start: int
    width: int
    destination_range_start: int

    def domain() -> Interval:
        return Interval(self.range_start, self.range_start + self.width)

    def codomain() -> Interval:
        return Interval(self.destination_range_start, self.destination_range_start + self.width)

    def last_included_number(self) -> int:
        return self.range_start + self.width - 1

    def apply(num: int) -> int:
        if num in range(self.range_start, self.range_start + self.width):
            return num - self.range_start + self.destination_range_start
        return num

    def unapply(num: int) -> int:
        if num in range(self.destination_range_start, self.destination_range_start + self.width):
            return num - self.destination_range_start + self.range_start
        return num


class Interval:
    begin: int
    end: int

    def __contains__(self, num):
        return num in range(self.begin, end)

    def difference(self, other: Interval) -> list[Interval]:
        # the other is bigger than us
        if self.begin in other and self.end - 1 in other:
            return []

        # the other is disjoint from us
        if not (other.begin in self or other.end - 1 in self):
            return [self]

        # the other is partial overlapped with us
        if other.begin in self and other.end - 1 in self:
            return [Interval(self.begin, other.begin), Interval(other.end, self.end)]

        if other.begin in self:
            return Interval(self.begin, other.begin)
        else:
            return Interval(other.end, self.end)

    def intersection(self, other: Interval) -> Interval | None:
        # the other is bigger than us
        if self.begin in other and self.end - 1 in other:
            return self

        # the other is disjoint from us
        if not (other.begin in self or other.end - 1 in self):
            return None

        # the other is partial overlapped with us
        return Interval(max(self.begin, other.begin), min(self.end, other.end))


def compose(
    f: PartialLinearMapping,
    g: PartialLinearMapping,
) -> tuple[list[PartialLinearMapping], list[PartialLinearMapping]]:
    """
    the left element is the old domain mapped in the new one
    the right element is the new domain remaining from the partial function applied to the old one (basically its the non overlapping
    domain of the second function with the codomain of the first)
    """
    f_o_g_domain = f.codomain().intersection(g.domain())

    # this is a list, we need to compute all the intervals that comes from here
    f_minus_g = f.codomain().difference(g.domain())

    # this is uncomplete/wrong, I'm missing the
    old_domain_mapped = list(
        lambda x: x is None,
        filter(
            [
                PartialLinearMapping(
                    f.range_start,
                    f.unapply(f_o_g_domain.begin),
                    f.destination_range_start
                ),
                PartialLinearMapping(
                    f_o_g_domain.begin,
                    f_o_g_domain.end,
                    g.destination_range_start
                )
            ]
        )
    )