Problem A
Att Klippa en Rektangel

Irus hade en rektangel. Hann klippte rektangeln och fick två rektanglar. Han lade sedan en åt sidan och klippte den andra och fortsatte att klippa på samma sätt (han klipper aldrig rektanglar som har lagts åt sidan) tills han hade $K$ rektanglar.

Efter att han sorterade rektanglarna efter längden på deras längre kanter insåg Irus att alla dessa längder är olika (längden på kortare kanterna behöver dock inte vara olika).

Uppgift

Irus glömde måtten på den ursprungliga rektangeln. Hjälp Irus komma ihåg dem.

Indata

Den första linjen innehåller antalet rektanglar $K$.

De återstående $K$ linjerna innehåller två naturliga tal vardera, $a_ i$ och $b_ i$, som är kantlängderna på rektangel nummer $i$, och dessa nummer är ordnade så att $a_ i \ge v_ i$ och $a_1 < \cdots < a_ K$.

Utdata

På den första linjen, skriv ut $P$ - det totala antalet möjliga mått för ursprungliga rektangeln.

På de nästa $P$ rader, skriv ut längden på kortare kanterna på alla möjliga ursprungliga rektanglar, från minsta till största (observera att vi räknar en rektangel med vissa mått högst en gång, även om det finns flera sätt att skära den i de $K$ givna rektanglarna).

Begränsningar

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

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

Delpoäng

Exempel

Den ursprungliga rektangeln kunde ha varit antingen $2 \times 8$ eller $4 \times 4$.

3
2 1
3 2
4 2

2
2
4