# given: values > 0

# returns (min, pod) found element and it's value and position in input
def find_min(vals):
    min_val, min_idx = None, -1
    for idx, val in enumerate(vals):
        if val < 0:
            continue

        if min_val is None or val < min_val:
            min_val = val
            min_idx = idx

    return min_val, min_idx


def merge_lists(lists):
    result = []
    window = [None] * len(lists)
    indices = [0] * len(lists)

    # O(len(aws) + len(azure) + len(GCP))
    while True:
        # collect current value for each csp
        for c in range(len(lists)):
            curr_csp = lists[c]
            idx = indices[c]
            v = curr_csp[idx] if idx < len(lists[c]) else -1
            window[c] = v

        # find min v, increment idx for given list, ignore Nones
        min_val, min_idx = find_min(window)

        if min_val is None:
            break

        result.append(min_val)
        indices[min_idx] += 1
    return result


aws = [34, 45, 47, 98]
azure = [1, 56, 89]
GCP = [2, 7, 78, 103, 204]

# (input, expected) pairs
cases = [
    ([aws, azure, GCP], [1, 2, 7, 34, 45, 47, 56, 78, 89, 98, 103, 204]),
    ([], []),
    ([[]], []),
    ([[1, 2, 3], []], [1, 2, 3]),
    ([[1, 2, 3]], [1, 2, 3]),
    ([[1, 2, 3], [1, 2, 3]], [1, 1, 2, 2, 3, 3]),
    ([[1, 2, 3], [4, 5, 6]], [1, 2, 3, 4, 5, 6]),
    ([[1, 20, 300], [2, 32, 302], [3, 33, 303]], [1, 2, 3, 20, 32, 33, 300, 302, 303]),
]

for c in cases:
    input_, expected = c
    result = merge_lists(input_)
    print(result)
    assert result == expected