You maintain a calendar of busy blocks as a list of intervals [start, end) that is already sorted by start and contains no overlaps (consecutive blocks may touch but never overlap). A new booking arrives; insert it and merge any intervals it now overlaps or touches, so that the calendar stays sorted and non-overlapping.
Two intervals are merged when they overlap or touch: [a, b) and [c, d) combine if c <= b and a <= d.
Input format
Line 1: an integer n — the number of existing intervals (may be 0).
Next n lines: two integers start end for each existing interval, sorted by start, pairwise non-overlapping.
Last line: two integers start end — the new interval to insert.
Output format
Line 1: an integer k — the number of intervals after inserting and merging.
Next k lines: two integers start end for each resulting interval, in ascending order of start. This ordering makes the answer unique.
Constraints
- 0 <= n <= 100000
- -1000000000 <= start < end <= 1000000000 for every interval, including the new one
- The
nexisting intervals are sorted by start and pairwise non-overlapping.