from typing import List, Literal


class Semver:
    def __init__(self, major: int, minor: int, patch: int):
        self.major = major
        self.minor = minor
        self.patch = patch

    def __str__(self):
        return f'{self.major}.{self.minor}.{self.patch}'

    def __eq__(self, other):
        return self.major == other.major and \
            self.minor == other.minor and \
            self.patch == other.patch

    def __lt__(self, other):
        if self.major < other.major:
            return True
        elif self.major == other.major:
            if self.minor < other.minor:
                return True
            elif self.minor == other.minor:
                return self.patch < other.patch
        return False

    def __gt__(self, other):
        if self.major > other.major:
            return True
        elif self.major == other.major:
            if self.minor > other.minor:
                return True
            elif self.minor == other.minor:
                return self.patch > other.patch
        return False

    def __le__(self, other):
        return self < other or self == other

    def __ge__(self, other):
        return self > other or self == other

    def __hash__(self):
        return hash((self.major, self.minor, self.patch))


class PackageVersion:
    def __init__(self, version: Semver, dependencies: List["SemverConstraint"] = []):
        self.version = version
        self.dependencies = dependencies


class Package:
    def __init__(self, name: str, versions: List[PackageVersion]):
        self.name = name
        self.versions = versions

    def max_satisfying_version(self, constraints: List["SemverConstraint"]):
        max_version = None
        for version in self.versions:
            if all([constraint.satisfies(version.version) for constraint in constraints]):
                if max_version is None or version.version > max_version.version:
                    max_version = version
        return max_version


class SemverConstraint:
    def __init__(
        self,
        package: str,
        constraint: Literal["==", ">=", "<=", ">", "<"],
        version: Semver,
    ):
        self.package = package
        assert constraint in ["==", ">=", "<=", ">", "<"], \
            f'Constraint must be one of "==", ">=", "<=", ">", "<", not {constraint}'
        self.constraint = constraint
        self.version = version

    def __str__(self):
        return f'{self.package} {self.constraint} {self.version}'

    def satisfies(self, version: Semver):
        if self.constraint == "==":
            return version == self.version
        elif self.constraint == ">=":
            return version >= self.version
        elif self.constraint == "<=":
            return version <= self.version
        elif self.constraint == ">":
            return version > self.version
        elif self.constraint == "<":
            return version < self.version