Problem A
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).

Task

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

Input

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 \ge b_ i$, and $a_1 < \cdots < a_ K$.

Output

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).

Constraints

• $2 \leq K \leq 100\, 000$

• $1 \leq b\_ i \leq a\_ i < a\_ {i+1} \le 5\, 000\, 000$ (for all $1 \leq i \leq K$).

Subtasks

Examples

The initial rectangle could have been either $2 \times 8$, or $4 \times 4$.

3
2 1
3 2
4 2

2
2
4