Merge Overlapping Intervals

You are given two lists of closed intervals. Each interval is represented by two integers, where the first integer is the starting point and the second integer is the ending point. Your task is to merge all overlapping intervals from both lists and output the resulting list of non-overlapping intervals, sorted by their starting values. An interval [a, b] is said to overlap with [c, d] if ( c \leq b ) and ( a \leq d ).

Formally, given a set of intervals ( I_i = [a_i, b_i] ) sorted by ( a_i ), merge consecutive intervals if ( a_{i+1} \leq b_i ).

inputFormat

The input is read from standard input (stdin) with the following format:

(n) (m>

The first line contains two integers (n) and (m), representing the number of intervals in the first and second list respectively. The next (n) lines each contain two integers denoting an interval in the first list. The following (m) lines each contain two integers denoting an interval in the second list.

outputFormat

Print the merged list of intervals to standard output (stdout). Each merged interval should be output on a separate line as two space-separated integers representing the start and end of the interval.## sample

3 3
1 3
5 7
9 12
2 6
8 10
13 15

1 7
8 12
13 15