def insert_interval(intervals, new):
    start, end = new
    output = []
    i = 0
    while i < len(intervals) and intervals[i][1] < start:
        output.append(list(intervals[i]))
        i += 1
    while i < len(intervals) and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    output.append([start, end])
    output.extend(list(pair) for pair in intervals[i:])
    return output