Tima ו-$N$ חבריו אוהבים לשחק ב-Bootfall. המשחק Bootfall הוא משחק ספורט עבור $N + 1$ שחקנים. לכל שחקן יש עוצמה, הניתנת לייצוג כמספר שלם חיובי. המשחק מורכב מ-$N + 1$ סיבובים; בכל סיבוב אחד השחקנים מצלם את הסיבוב בווידאו ושאר $N$ השחקנים מתחלקים לשתי קבוצות, כך שכל שחקן משובץ לאחת הקבוצות ושתי הקבוצות אינן ריקות. עוצמתה של קבוצה היא סכום העוצמות של כל השחקנים בקבוצה. בנוסף, כל שחקן ישמש כמצלם בסיבוב אחד בדיוק.

סיבוב נקרא תיקו אם קיימת חלוקה לשתי קבוצות בעלות עוצמה שווה, וכן המשחק כולו נקרא ידידותי אם כל הסיבובים הם תיקו. כל אחד מ-$N$ החברים כבר עדכן את Tima לגבי עוצמתו, וכעת Tima יכול לקבוע לעצמו כל ערך חוקי של עוצמה.

Tima יודע את העוצמות של כל $N$ השחקנים והוא יבחר ערך כלשהו כך שהמשחק יוכל להיות ידידותי. עזרו לו למצוא את כל ערכי העוצמה האפשריים.

קלט

השורה הראשונה של הקלט מכילה מספר שלם חיובי אחד $N$ ($1 \le N \le 500$) — מספר החברים של Tima. השורה השנייה של הקלט מכילה $N$ מספרים שלמים חיוביים $a_1, a_2, \ldots, a_N$ ($1 \le a_i \le 500$; $1 \le i \le N$) מופרדים ברווחים, כאשר $a_i$ הוא העוצמה של האדם ה-$i$.

פלט

השורה הראשונה של הפלט חייבת להכיל מספר שלם אחד $K$ — מספר ערכי העוצמה האפשריים עבור Tima. אם אין אף עוצמה אפשרית עבור Tima, הדפיסו רק "0" (ללא מירכאות); אחרת, בשורה השנייה של הפלט הדפיסו $K$ מספרים שלמים חיוביים מופרדים ברווחים — כל ערכי העוצמה האפשריים עבור Tima בסדר עולה.

תתי-משימות

בעיה זו מורכבת משש תתי-משימות:

1. $1 \le N \le 12$, $1 \le a_i \le 200$, לכל $1 \le i \le N$. ניקוד: 6 נקודות.
2. $1 \le N \le 30$, $1 \le a_i \le 20$, לכל $1 \le i \le N$. ניקוד: 7 נקודות.
3. $1 \le N \le 100$, $1 \le a_i \le 100$, לכל $1 \le i \le N$. ניקוד: 15 נקודות.
4. $1 \le N \le 270$, $1 \le a_i \le 270$, לכל $1 \le i \le N$. ניקוד: 16 נקודות.
5. $1 \le N \le 350$, $1 \le a_i \le 350$, לכל $1 \le i \le N$. ניקוד: 21 נקודות.
6. $1 \le N \le 500$, $1 \le a_i \le 500$, לכל $1 \le i \le N$. ניקוד: 35 נקודות.

כל תת-משימה תזכה בניקוד רק אם הפתרון עובר בהצלחה את כל תתי-המשימות הקודמות.

דוגמאות

קלט 1

4
1 3 1 5

פלט 1

1
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

הערה

הערות למבחן הדוגמה הראשון.

נראה כי אם 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$, אז המשחק אינו יכול להיות ידידותי.