Tima og $N$ vinir hans elska að spila Bootfall. Bootfall er íþróttaleikur fyrir $N + 1$ leikmenn. Hver leikmaður hefur styrk sem má tákna sem jákvæða heiltölu. Leikurinn samanstendur af $N + 1$ umferðum; í hverri umferð tekur einn leikmannanna umferðina upp á myndband og hinir $N$ leikmennirnir skiptast í tvö lið, þannig að hverjum leikmanni er skipað í annað hvort liðið og bæði liðin eru ekki tóm. Styrkur liðs er summa styrkja allra leikmanna í liðinu. Auk þess mun hver leikmaður sjá um upptökuna í nákvæmlega einni umferð.

Umferð kallast jafntefli ef til er skipting í tvö lið með jafnan styrk, og allur leikurinn kallast vináttuleikur ef allar umferðir eru jafntefli. Hver og einn af vinunum $N$ hefur þegar sagt Tima frá styrk sínum, og nú getur Tima gefið sjálfum sér hvaða gilda styrkgildi sem er.

Tima þekkir styrk allra $N$ leikmannanna og hann mun velja eitthvert gildi þannig að leikurinn geti orðið vináttuleikur. Hjálpaðu honum að finna alla mögulega styrki.

Inntak

Fyrsta lína inntaksins inniheldur eina jákvæða heiltölu $N$ ($1 \le N \le 500$) — fjölda vina Tima. Önnur lína inntaksins inniheldur $N$ jákvæðar heiltölur $a_1, a_2, \ldots, a_N$ ($1 \le a_i \le 500$; $1 \le i \le N$) aðskildar með bili, þar sem $a_i$ er styrkur $i$-tu manneskjunnar.

Úttak

Fyrsta lína úttaksins verður að innihalda eina heiltölu $K$ — fjölda mögulegra styrkja fyrir Tima. Ef enginn mögulegur styrkur er til fyrir Tima skal prenta aðeins „0“ (án gæsalappa); annars skal á annarri línu úttaksins prenta $K$ jákvæðar heiltölur aðskildar með bili — öll möguleg styrkgildi fyrir Tima í hækkandi röð.

Undirverkefni

Þetta verkefni samanstendur af sex undirverkefnum:

1. $1 \le N \le 12$, $1 \le a_i \le 200$, fyrir öll $1 \le i \le N$. Stig: 6 stig.
2. $1 \le N \le 30$, $1 \le a_i \le 20$, fyrir öll $1 \le i \le N$. Stig: 7 stig.
3. $1 \le N \le 100$, $1 \le a_i \le 100$, fyrir öll $1 \le i \le N$. Stig: 15 stig.
4. $1 \le N \le 270$, $1 \le a_i \le 270$, fyrir öll $1 \le i \le N$. Stig: 16 stig.
5. $1 \le N \le 350$, $1 \le a_i \le 350$, fyrir öll $1 \le i \le N$. Stig: 21 stig.
6. $1 \le N \le 500$, $1 \le a_i \le 500$, fyrir öll $1 \le i \le N$. Stig: 35 stig.

Hvert undirverkefni gefur aðeins stig ef lausnin stenst öll fyrri undirverkefni.

Dæmi

Inntak 1

4
1 3 1 5

Úttak 1

1
3

Inntak 2

6
3 5 7 11 9 13

Úttak 2

4
1 3 17 19

Inntak 3

3
2 2 2

Úttak 3

0

Inntak 4

4
200 200 200 200

Úttak 4

2
200 600

Athugasemd

Athugasemdir við fyrsta sýnidæmið.

Sýnum fram á að ef Tima velur styrkinn $3$, þá getur leikurinn orðið vináttuleikur.

• Þegar Tima tekur leikinn upp má skipta hinum leikmönnunum svona til að umferðin verði jafntefli: $(1, 3, 1)$ í fyrra liðinu og $(5)$ í því síðara.
• Þegar vinur 1 tekur leikinn upp má skipta hinum svona: $(1, 5)$ í fyrra liðinu, $(3, 3)$ í því síðara.
• Þegar vinur 2 tekur leikinn upp má skipta hinum svona: $(1, 1, 3)$ í fyrra liðinu, $(5)$ í því síðara.
• Þegar vinur 3 tekur leikinn upp má skipta hinum svona: $(3, 3)$ í fyrra liðinu, $(1, 5)$ í því síðara.
• Þegar vinur 4 tekur leikinn upp má skipta hinum svona: $(1, 3)$ í fyrra liðinu, $(1, 3)$ í því síðara.

Ef Tima velur styrk sem er ekki jafn $3$, þá getur leikurinn ekki orðið vináttuleikur.