Cutting a Rectangle

Time limit1sMemory limit1024 MB

Summary

Given K rectangles with distinct longer sides, find every possible shorter side of an original rectangle that can be cut into exactly these pieces.

Level: Medium7 of 10
Topics: Math, Sorting, Greedy
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Constraints

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

Examples2

Example 1
Input
```
3
2 1
3 2
4 2
```
Expected output
```
2
2
4
```
Example 2
Input
```
5
1 1
2 1
3 1
4 3
6 3
```
Expected output
```
3
3
4
6
```