Combine Two Vectors of Intervals (MLE)

Given two lists of closed intervals, where the intervals within each list do not overlap. Combine the intervals of both lists, merge all intervals that intersect, and output them in ascending order of start. Equal endpoints count as overlapping: for example, [1,2] and [2,3] merge into [1,3], while [1,2] and [3,4] cannot be merged.

输入格式

This site's input: the first line contains n m (0..100000), followed by n lines for X and then m lines for Y, each line being l r (−10⁹≤l≤r≤10⁹). The intervals within each list do not overlap but may be unsorted.

输出格式

The first line is the number k of merged intervals, followed by k lines of l r in ascending order of start; if everything is empty, output 0.

样例 1

输入：

3 3
1 5
10 14
16 18
2 6
8 10
11 20

输出：

2
1 6
8 20

样例 2

输入：

1 1
1 2
2 3

输出：

1
1 3

样例 3

输入：

0 0

输出：

0

样例说明

Example 1: 1..5 and 2..6 merge into 1..6; 8..10, 10..14, 11..20, and 16..18 are connected and merge into 8..20.

Example 2: the closed intervals meet at endpoint 2, so a single interval 1 3 is output.

Example 3: both lists are empty, so the merged count is 0.