Merge Overlapping Intervals

You are given several intervals represented as a pair of integers [start, end]. Your task is to merge all overlapping intervals. Two intervals overlap if they share at least one point (i.e. \(a\) interval [\(s_1, e_1\)] and [\(s_2, e_2\)] overlap if \(s_2 \le e_1\)). The merged interval is defined by the minimum start and the maximum end of the overlapping intervals.

In the input, the first line contains an integer \(T\) denoting the number of test cases. Each test case starts with an integer \(n\) indicating the number of intervals, followed by \(n\) lines each containing two space-separated integers. For each test case, output the merged intervals sorted by their start times. Each merged interval should be printed as two space-separated integers. The intervals for each test case must be printed in a single line and multiple test cases should be separated by a newline.

inputFormat

The input is read from standard input (stdin).\nThe first line contains an integer T, the number of test cases. For each test case, the first line is an integer n, the number of intervals. Each of the next n lines contains two integers representing the start and end of an interval.

outputFormat

For each test case, output a single line containing the merged intervals. Each interval is represented by two space-separated integers (start and end). Intervals within a test case are separated by a space, and different test cases are separated by newline.## sample

1
3
1 2
3 4
5 6

1 2 3 4 5 6