7263번 - Cutting a rectangle 서브태스크다국어

Irus had a rectangle. Irus cut the rectangle and obtained two rectangles. He then put one aside and cut the other one, and continued cutting the same way (never cutting rectangles that were put aside) until he had K rectangles. The edges of all the rectangles have integer lengths.

After he sorted the rectangles by the lengths of their longer edges, Irus realized that these lengths are all distinct (however the lengths of the shorter edges need not be distinct).

Irus forgot the dimensions of the initial rectangle. Help Irus remember them.

The first line contains the number of rectangles K. The remaining K lines contain two natural numbers each, a_i and b_i, which are the edge lengths of the i-th rectangle, and these numbers are ordered so that a_i ≥ b_i, and a₁ < · · · < a_K.

In the first line, output P – the total number of possible dimensions of the initial rectangle.

In the next P lines, output the lengths of the shorter edges of all possible initial rectangles, from smallest to largest (note that we count a rectangle of certain dimensions at most once, even if there are several ways to cut it into the K given rectangles).

• 2 ≤ K ≤ 100 000
• 1 ≤ b_i ≤ a_i < a_i+1 ≤ 5 000 000 for all values of i