Tima og de $N$ vennene hans elsker å spille Bootfall. Bootfall er et sportsspill for $N + 1$ spillere. Hver spiller har en styrke, som kan representeres som et positivt heltall. Et spill består av $N + 1$ runder; i hver runde tar én av spillerne opp runden på video, og de resterende $N$ spillerne deler seg inn i to lag, slik at hver spiller blir tildelt ett av lagene og begge lagene er ikke-tomme. Styrken til et lag er summen av styrkene til alle spillerne på laget. I tillegg vil hver spiller være den som filmer i nøyaktig én runde.

En runde kalles uavgjort hvis det finnes en inndeling i to lag med lik styrke, og hele spillet kalles vennskapelig hvis alle rundene er uavgjorte. Hver av de $N$ vennene har allerede fortalt Tima om styrken sin, og nå kan Tima gi seg selv en hvilken som helst gyldig styrkeverdi.

Tima kjenner styrkene til alle de $N$ spillerne, og han vil velge en verdi slik at spillet kan bli vennskapelig. Hjelp ham med å finne alle mulige styrker.

Inndata

Den første linjen av inndata inneholder ett positivt heltall $N$ ($1 \le N \le 500$) — antallet venner av Tima. Den andre linjen av inndata inneholder $N$ positive heltall $a_1, a_2, \ldots, a_N$ ($1 \le a_i \le 500$; $1 \le i \le N$) atskilt med mellomrom, der $a_i$ er styrken til den $i$-te personen.

Utdata

Den første linjen av utdata må inneholde ett heltall $K$ — antallet mulige styrker for Tima. Hvis det ikke finnes noen mulig styrke for Tima, skriv bare ut «0» (uten anførselstegn); ellers skal du på den andre linjen av utdata skrive ut $K$ positive heltall atskilt med mellomrom — alle mulige styrkeverdier for Tima i stigende rekkefølge.

Deloppgaver

Denne oppgaven består av seks deloppgaver:

1. $1 \le N \le 12$, $1 \le a_i \le 200$, for alle $1 \le i \le N$. Poengsum: 6 poeng.
2. $1 \le N \le 30$, $1 \le a_i \le 20$, for alle $1 \le i \le N$. Poengsum: 7 poeng.
3. $1 \le N \le 100$, $1 \le a_i \le 100$, for alle $1 \le i \le N$. Poengsum: 15 poeng.
4. $1 \le N \le 270$, $1 \le a_i \le 270$, for alle $1 \le i \le N$. Poengsum: 16 poeng.
5. $1 \le N \le 350$, $1 \le a_i \le 350$, for alle $1 \le i \le N$. Poengsum: 21 poeng.
6. $1 \le N \le 500$, $1 \le a_i \le 500$, for alle $1 \le i \le N$. Poengsum: 35 poeng.

Hver deloppgave gir poeng kun dersom løsningen består alle de foregående deloppgavene.

Eksempler

Inndata 1

4
1 3 1 5

Utdata 1

1
3

Inndata 2

6
3 5 7 11 9 13

Utdata 2

4
1 3 17 19

Inndata 3

3
2 2 2

Utdata 3

0

Inndata 4

4
200 200 200 200

Utdata 4

2
200 600

Merknad

Merknader til det første eksempeltesttilfellet.

La oss vise at hvis Tima velger styrken $3$, så kan spillet bli vennskapelig.

• Når Tima filmer spillet, kan de andre spillerne deles inn slik for å gjøre runden uavgjort: $(1, 3, 1)$ på det første laget og $(5)$ på det andre.
• Når venn 1 filmer spillet, kan de andre deles inn slik: $(1, 5)$ på det første laget, $(3, 3)$ på det andre.
• Når venn 2 filmer spillet, kan de andre deles inn slik: $(1, 1, 3)$ på det første laget, $(5)$ på det andre.
• Når venn 3 filmer spillet, kan de andre deles inn slik: $(3, 3)$ på det første laget, $(1, 5)$ på det andre.
• Når venn 4 filmer spillet, kan de andre deles inn slik: $(1, 3)$ på det første laget, $(1, 3)$ på det andre.

Hvis Tima velger en styrke som ikke er lik $3$, kan spillet ikke bli vennskapelig.