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 i \le N$ үшін $1 \le N \le 12$, $1 \le a_i \le 200$. Ұпайы: 6 ұпай.
2. Барлық $1 \le i \le N$ үшін $1 \le N \le 30$, $1 \le a_i \le 20$. Ұпайы: 7 ұпай.
3. Барлық $1 \le i \le N$ үшін $1 \le N \le 100$, $1 \le a_i \le 100$. Ұпайы: 15 ұпай.
4. Барлық $1 \le i \le N$ үшін $1 \le N \le 270$, $1 \le a_i \le 270$. Ұпайы: 16 ұпай.
5. Барлық $1 \le i \le N$ үшін $1 \le N \le 350$, $1 \le a_i \le 350$. Ұпайы: 21 ұпай.
6. Барлық $1 \le i \le N$ үшін $1 \le N \le 500$, $1 \le a_i \le 500$. Ұпайы: 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$-ке тең емес күшті таңдаса, онда ойын жолдастық бола алмайды.