Tima та його $N$ друзів люблять грати в Bootfall. Bootfall — це спортивна гра для $N+1$ гравців. Кожен гравець має силу, яку можна подати додатним цілим числом. Гра складається з $N+1$ раундів. У кожному раунді один із гравців знімає раунд на відео, а решта $N$ гравців діляться на дві команди так, щоб кожен гравець належав до однієї з команд і обидві команди були непорожніми. Сила команди дорівнює сумі сил усіх її гравців. Крім того, кожен гравець знімає відео рівно в одному раунді.

Раунд називають нічийним, якщо існує поділ на дві команди з однаковою силою. Усю гру називають дружньою, якщо всі раунди нічийні. Кожен із $N$ друзів уже повідомив Tima свою силу, і тепер Tima може призначити собі будь-яке допустиме значення сили.

Tima знає сили всіх $N$ гравців і вибере таке значення, щоб гра могла бути дружньою. Допоможіть йому знайти всі можливі значення сили.

Вхідні дані

Перший рядок містить одне додатне ціле число $N$ ($1\le N\le500$) — кількість друзів Tima. Другий рядок містить $N$ додатних цілих чисел $a_1,a_2,\ldots,a_N$ ($1\le a_i\le500$; $1\le i\le N$), розділених пробілами, де $a_i$ — сила $i$-го друга.

Вихідні дані

Перший рядок має містити одне ціле число $K$ — кількість можливих значень сили Tima. Якщо таких значень немає, виведіть лише «0» (без лапок). Інакше в другому рядку виведіть $K$ додатних цілих чисел, розділених пробілами, — усі можливі значення сили Tima в порядку зростання.

Оцінювання

Задача складається із шести підзадач:

1. $1\le N\le12$, $1\le a_i\le200$ для всіх $1\le i\le N$. 6 балів.
2. $1\le N\le30$, $1\le a_i\le20$ для всіх $1\le i\le N$. 7 балів.
3. $1\le N\le100$, $1\le a_i\le100$ для всіх $1\le i\le N$. 15 балів.
4. $1\le N\le270$, $1\le a_i\le270$ для всіх $1\le i\le N$. 16 балів.
5. $1\le N\le350$, $1\le a_i\le350$ для всіх $1\le i\le N$. 21 бал.
6. $1\le N\le500$, $1\le a_i\le500$ для всіх $1\le i\le N$. 35 балів.

Бали за підзадачу нараховують лише тоді, коли розв'язок успішно проходить усі попередні підзадачі.

Приклади

Вхідні дані 1

4
1 3 1 5

Вихідні дані 1

1
3

Примітка

Пояснення до першого прикладу.

Покажемо, що коли Tima вибере силу $3$, гра може бути дружньою.

• Коли Tima знімає гру, для нічиєї інші гравці можуть поділитися так: $(1,3,1)$ у першій команді та $(5)$ у другій.
• Коли друг 1 знімає гру, інші можуть поділитися так: $(1,5)$ у першій команді та $(3,3)$ у другій.
• Коли друг 2 знімає гру, інші можуть поділитися так: $(1,1,3)$ у першій команді та $(5)$ у другій.
• Коли друг 3 знімає гру, інші можуть поділитися так: $(3,3)$ у першій команді та $(1,5)$ у другій.
• Коли друг 4 знімає гру, інші можуть поділитися так: $(1,3)$ у першій команді та $(1,3)$ у другій.

Якщо Tima вибере силу, відмінну від $3$, гра не може бути дружньою.

Вхідні дані 2

6
3 5 7 11 9 13

Вихідні дані 2

4
1 3 17 19

Вхідні дані 3

3
2 2 2

Вихідні дані 3

0

Вхідні дані 4

4
200 200 200 200

Вихідні дані 4

2
200 600