Cutting a Rectangle

Irus had a single rectangle whose sides have integer lengths. He cut the rectangle with one straight line parallel to a side, splitting it into two rectangles, set one of them aside (a rectangle that has been set aside is never cut again), and kept cutting the other one in the same way. He repeated this until he had $K$ rectangles in total; every rectangle produced this way has integer side lengths.

When Irus sorted the $K$ resulting rectangles by the length of their longer edge, he found that these longer-edge lengths were all distinct (the shorter-edge lengths, however, may coincide).

Irus has forgotten the size of the original rectangle. Help him by finding every possible size of the initial rectangle.

The first line contains the number of rectangles $K$. Each of the next $K$ lines contains two natural numbers $a_i$ and $b_i$, the side lengths of the $i$-th rectangle. They are given so that $a_i \ge b_i$, and they are ordered so that $a_1 < a_2 < \cdots < a_K$.

On the first line, print $P$, the number of possible sizes of the initial rectangle.

On each of the next $P$ lines, print the length of the shorter edge of one possible initial rectangle, in increasing order (a rectangle of a given size is counted only once, even if there are several ways to cut it into the $K$ given rectangles).

• $2 \le K \le 100000$
• $1 \le b_i \le a_i < a_{i+1} \le 5000000$ for all $i$