def insert_interval(existing_intervals, new_interval):
    # Read the starting and ending time of the new interval, into separate variables
    new_start, new_end = new_interval[0], new_interval[1]
    print("The new interval starts at ", new_start,
          " and ends at ", new_end, ".", sep="")
    # Initialize variables to help in iterating over the existing intervals list
    i = 0
    n = len(existing_intervals)
    print("There are", n, "intervals present in the list already. We append the intervals that have the starting point smaller than our new interval to add.")
    # Initialize an empty list to store the output
    output = []

    # Append all intervals that start before the new interval to the output list
    while i < n and existing_intervals[i][0] < new_start:
        output.append(existing_intervals[i])
        i = i + 1
    print("The output before we add the new interval is:", output)
    # If the new interval starts after the end of the last interval appended to the output list,
    # just append the new interval to the output list.
    if not output or output[-1][1] < new_start:
        output.append(new_interval)
    # Otherwise merge the two intervals
    else:
        output[-1][1] = max(output[-1][1], new_end)

        # Copy any remaining intervals to the output list,
    # similarly merging any overlaping intervals as we go
    while i < n:
        ei = existing_intervals[i]
        start, end = ei[0], ei[1]
        if output[-1][1] < start:
            output.append(ei)
        else:
            output[-1][1] = max(output[-1][1], end)
        i += 1
    print("The output after we add new interval and merge the overlapping intervals is going to be:", output)
    return output


# Driver code
def main():
    new_interval = [[5, 7], [8, 9], [10, 12], [1, 3], [1, 10]]
    existing_intervals = [
        [[1, 2], [3, 5], [6, 8]],
        [[1, 3], [5, 7], [10, 12]],
        [[8, 10], [12, 15]],
        [[5, 7], [8, 9]],
        [[3, 5]]
    ]
    
    for i in range(len(new_interval)):
        print("Exiting intervals: ", existing_intervals[i], sep="")
        print("New interval: ", new_interval[i], sep="")
        output = insert_interval(existing_intervals[i], new_interval[i])
        print("-"*100)


if __name__ == "__main__":
    main()