Problem A
Ein Rechteck aufschneiden

Irus hatte ein Rechteck, das er zunächst in zwei Rechtecke aufgeschnitten hat. Anschließend hat er eins der Rechtecke weggelegt und hat das andere wieder aufgeschnitten und immer so weitergemacht (Er hat nie weggelegte Rechtecke wieder aufgeschnitten) bis er am Ende $K$ Rechtecke hatte.

Nachdem er die entstandenen Rechtecke nach der Länge der jeweils längeren Seite sortiert hat, bemerkte er, dass die entstandenen Längen alle paarweise verschieden sind. (Die jeweils kürzeren Seiten müssen jedoch nicht paarweise verschieden sein.)

Aufgabe

Irus hat die Maße des ursprünglichen Rechtecks vergessen. Hilf ihm, sich wieder daran zu erinnern.

Eingabe

Die erste Zeile enthält die Anzahl $K$ der Rechtecke.

Die verbleibenden $K$ Zeilen enthalten je zwei natürliche Zahlen, $a_ i$ und $b_ i$, die die Seitenlängen des $i$-ten Rechtecks angeben. Diese sind so geordnet, dass $a_ i\geq b_ i$ und $a_1 < \cdots < a_ K$.

Ausgabe

Gib in der ersten Zeile die insgesamt mögliche Anzahl $P$ an Seitenverhältnissen des ursprünglichen Rechtecks aus.

Gib anschließend in den nächsten $P$ Zeilen jeweils die Längen der kürzeren Seiten aller möglichsten Ausgangsrechtecke, sortiert von kurz nach lang, aus. (Wir zählen ein Rechteck mit bestimmten Maßen nur einmal, auch wenn es mehrere Möglichkeiten gibt, dieses in die $K$ gegebenen aufzuschneiden.)

Beschränkungen

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

• $1 \leq b\_ i \leq a\_ i < a\_ {i+1} \le 5\, 000\, 000$ (für alle $1 \leq i \leq K$).

Teilaufgaben

Beispiele

Das Ausgangsrechteck kann entweder $2 \times 8$ oder $4 \times 4$ groß gewesen sein.

3
2 1
3 2
4 2

2
2
4