Nested Interval Chain Construction

Given n intervals, Mirko wants to construct a sequence of intervals I₁, I₂, …, I_k such that every subsequent interval is a proper subinterval of the previous one (\subset), and every integer within each constructed interval is contained in at least one of the given intervals.

An interval [a, b] is considered valid if, for every integer x with a \le x \le b, there exists at least one input interval [L, R] satisfying L \le x \le R. To solve the problem, you should:

• Merge the given intervals to form the union of all covered positions.
• From the resulting union, select a longest contiguous segment [s, t].
• Construct the chain as follows:
  I₁ = [s, t]
  I₂ = [s+1, t-1]
  I₃ = [s+2, t-2]
  ...
  Continue until the constructed interval becomes invalid (i.e. when s+i > t-i).

The length of the chain is given by the formula: k = \left\lfloor \frac{t-s}{2} \right\rfloor + 1.

If there are multiple contiguous segments in the union, use the one with the maximum length to construct the longest chain possible. Your task is to output the chain length k and then the k intervals (each represented by its two endpoints) in order.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of intervals.

Each of the following n lines contains two integers L and R (L ≤ R) representing an interval.

outputFormat

On the first line, output k, the length of the constructed interval chain.

Each of the next k lines should contain two integers denoting the endpoints of the constructed intervals, in the order they were constructed.

sample

3
1 3
5 7
9 10

2
1 3
2 2