Problem A
Að Skera Rétthyrning

Irus átti rétthyrning. Irus skar rétthyrninginn niður og fékk tvo rétthyrninga úr því. Hann setti annan rétthyrninginn til hliðar og hélt áfram að skera hinn þar til hann átti $K$ rétthyrninga. Hann passar sig að skera aldrei rétthyrningana sem hann setur til hliðar. Hliðarlengdir rétthyrningana eru alltaf heiltölur.

Eftir að hafa skorið þá niður raðar hann rétthyrningunum eftir lengd lengri hliðarinnar. Irus áttaði sig þá á því að þessar hliðarlengdir væru allar mismunandi. Styttri hliðarlengdirnar þurfa hins vegar ekki að vera mismunandi.

Verkefni

Irus gleymdi hliðarlengdunum á upprunalega rétthyrningnum. Hjálpaðu Irus að muna þær.

Inntak

Fyrsta línan inniheldur fjölda rétthyrninga $K$.

Næstu $K$ línur innihalda tvær jákvæðar heiltölur hver, $a_i$ og $b_i$, sem eru hliðarlengdirnar á rétthyrning númer $i$. Tölurnar eru raðaðar þannig að $a_i\ge b_i$ og $a_1<\cdots <a_K$.

Úttak

Á fyrstu línunni skaltu skrifa út $P$ - fjölda möguleika fyrir hliðarlengdir upprunalega rétthyrningsins.

Á næstu $P$ línunum skaltu skrifa út möguleikana, einn möguleika á hverri línu, sem inniheldur þá einungis styttri hliðarlengdina á mögulega rétthyrningnum. Athugaðu að við skrifum styttri hliðarlengdina af tilteknum rétthyrning einu sinni þó það væru margar leiðir til að skera hann niður í gefnu $K$ rétthyrningana.

Takmarkanir

• $2\le K\le 100000$

• $1\le b\mathrm{\_}i\le a\mathrm{\_}i<a\mathrm{\_}i+1\le 5000000$ (fyrir öll $1\le i\le K$).

Hlutverkefni

Sýnidæmi

Upprunalegi rétthyrningurinn hefði getað verið $2\times 8$ eða $4\times 4$.

3
2 1
3 2
4 2

2
2
4