Merge Overlapping Intervals

You are given a list of intervals. Each interval is represented as a pair of integers \([\text{start}, \text{end}]\). Your task is to merge all overlapping intervals and print the resulting intervals in ascending order based on their start times.

An overlap occurs between two intervals \([a, b]\) and \([c, d]\) if \(c \le b\). When two intervals overlap, they should be merged into one interval \([\min(a,c), \max(b,d)]\). If there are no overlapping intervals, the original intervals should remain unchanged.

Note: The intervals provided might not be initially sorted. Your solution should work correctly regardless of the input order.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

N
start_1 end_1
start_2 end_2
... 
start_N end_N

Here, the first line contains a single integer \(N\), the number of intervals. Each of the next \(N\) lines contains two space-separated integers representing the start and end of an interval \( [\text{start}, \text{end}] \). If \(N = 0\), no intervals follow.

outputFormat

The output is written to standard output (stdout). The first line should contain a single integer \(M\), the number of merged intervals. Each of the next \(M\) lines should contain two space-separated integers representing the start and end of a merged interval. The merged intervals must be printed in ascending order by their start time.

## sample

4
1 3
2 4
5 7
6 8

2
1 4
5 8

</p>