Tima and his $N$ friends love to play Bootfall. Bootfall — is a sport game for $N + 1$ players. Each player has a strength, which can be represented as a positive integer number. Game consists of $N + 1$ rounds, in each round one of the players will record the round on video and rest of $N$ players divides into two teams, such that each player will be assigned to one of the teams and both teams are non-empty. Strength of the team is sum of the strengths of all players in team. Also, each player will be recorder in exactly one round.

Round called draw if exists division into two teams with equal strength, also whole game called friendly if all rounds are draw. Each of $N$ friends are already informed Tima about their strength, and now Tima can assign himself any valid value of strength.

Tima know the strengths of all $N$ players and he will choose some value, such that game can be friendly. Help him to find all possible strength.

Input

First line of input contains one positive integer number $N$ ($1 \le N \le 500$) — the number of friends of Tima. Second line of input contains $N$ positive integer numbers $a_1, a_2, \ldots, a_N$ ($1 \le a_i \le 500$; $1 \le i \le N$) separated with space, $a_i$ — strength of $i$-th person.

Output

First line of output must contain one integer number $K$ — number of possible strength for Tima. If there is no possible strength for Tima, then print only “0” (without quotes), otherwise on second line of output print $K$ positive integer numbers separated by space — all possible strength values for Tima in increasing order.

Subtasks

This problem consists of six subtasks:

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

Each subtask will be scored if only if the solution successfully passes all of the previous subtasks.

Examples

Input 1

4
1 3 1 5

Output 1

1
3

Input 2

6
3 5 7 11 9 13

Output 2

4
1 3 17 19

Input 3

3
2 2 2

Output 3

0

Input 4

4
200 200 200 200

Output 4

2
200 600

Note

Notes to first sample test.

Let us show, that if Tima selects strength $3$ then the game can be friendly.

• When Tima will record game, to make round draw other gamers may be divided as follows: $(1, 3, 1)$ in the first team, and $(5)$ in second.
• When friend $1$ will record game, others may be divided as follows: $(1, 5)$ in the first team, $(3, 3)$ in the second.
• When friend $2$ will record game, others may be divided as follows: $(1, 1, 3)$ in the first team, $(5)$ in the second.
• When friend $3$ will record game, others may be divided as follows: $(3, 3)$ in the first team, $(1, 5)$ in the second.
• When friend $4$ will record game, others may be divided as follows: $(1, 3)$ in the first team, $(1, 3)$ in the second.

If Tima selects strength not equal to $3$, then the game cannot be friendly.