Find the **earliest dependency version** that supports a target feature, using as few API probes as possible. ## What to implement ``` solution(versions, supported_versions) ``` - **`versions`** — a list of distinct version strings, each in the form `"major.minor.patch"` (numeric components, possibly zero-padded, e.g. `"104.000.01"`). The list is already sorted in ascending semantic-version order. - **`supported_versions`** — a list that simulates a black-box API `isSupported(v)`: a version supports the feature **if and only if** it appears in `supported_versions`. This list is always a subset of `versions`. Return the **earliest** (smallest in the sorted order) version string that supports the feature, or **`None`** if no version supports it. ## Why this isn't a plain search Support is **not monotonic** across the full version list: an early version may support the feature, a later version (in a new major or minor) may not, and an even later one may support again. So you cannot simply scan or binary-search the whole list directly. ## Structure guarantees (these make a sub-linear API strategy possible) The data obeys a three-level hierarchical pattern: 1. **Major level.** If any version supports the feature, there is a **first supporting major**, and every major after it also contains at least one supporting version. 2. **Minor level.** Inside that first supporting major, there is a **first supporting minor**, and every later minor within that major also contains at least one supporting version. 3. **Patch level.** Inside that first supporting major/minor pair, support is **monotonic by patch** among the listed versions — once support starts, it continues. Additionally, **if a major or a minor contains any supporting version, then its latest listed version is guaranteed to be supporting.** This lets you probe a single representative version per major and per minor. The earliest supporting version is therefore the first supporting patch inside the first supporting minor inside the first supporting major. ## Constraints - `0 <= len(versions) <= 200000` - `versions` is sorted ascending, all versions are distinct, and `supported_versions` is a subset of `versions`. - The support pattern always obeys the hierarchical guarantees above: if support exists at all, a first supporting major exists; within it a first supporting minor exists; within it a first supporting patch exists; and the latest listed version of any supporting major or minor is also supporting. ## Examples - `versions = ["103.003.01", "103.003.02", "103.004.01", "104.000.01", "104.001.01", "104.001.02", "105.000.01"]`, `supported_versions = ["103.004.01", "104.001.02", "105.000.01"]` → `"103.004.01"` - `versions = ["101.000.01", "101.001.01", "102.000.01", "102.000.02", "102.001.01", "103.000.01"]`, `supported_versions = ["102.000.02", "102.001.01", "103.000.01"]` → `"102.000.02"` - `versions = ["200.000.01"]`, `supported_versions = ["200.000.01"]` → `"200.000.01"` - `versions = ["300.000.01", "300.000.02"]`, `supported_versions = []` → `None` - `versions = []`, `supported_versions = []` → `None`

def solution(versions, supported_versions):
    if not versions:
        return None

    supported = set(supported_versions)

    major_order = []
    major_map = {}

    for v in versions:
        major_str, minor_str, _ = v.split('.')
        major = int(major_str)
        minor = int(minor_str)

        if major not in major_map:
            major_order.append(major)
            major_map[major] = {'latest': v, 'minor_order': [], 'minors': {}}

        major_info = major_map[major]
        major_info['latest'] = v

        if minor not in major_info['minors']:
            major_info['minor_order'].append(minor)
            major_info['minors'][minor] = {'latest': v, 'versions': []}

        minor_info = major_info['minors'][minor]
        minor_info['latest'] = v
        minor_info['versions'].append(v)

    def first_true(items, predicate):
        lo, hi = 0, len(items) - 1
        answer = None
        while lo <= hi:
            mid = (lo + hi) // 2
            item = items[mid]
            if predicate(item):
                answer = item
                hi = mid - 1
            else:
                lo = mid + 1
        return answer

    first_major = first_true(major_order, lambda major: major_map[major]['latest'] in supported)
    if first_major is None:
        return None

    major_info = major_map[first_major]
    first_minor = first_true(major_info['minor_order'], lambda minor: major_info['minors'][minor]['latest'] in supported)
    if first_minor is None:
        return None

    patch_versions = major_info['minors'][first_minor]['versions']
    lo, hi = 0, len(patch_versions) - 1
    answer = None

    while lo <= hi:
        mid = (lo + hi) // 2
        version = patch_versions[mid]
        if version in supported:
            answer = version
            hi = mid - 1
        else:
            lo = mid + 1

    return answer