Ра­дио­те­ле­скоп пы­та­ет­ся по­лу­чать и ана­ли­зи­ро­вать сиг­на­лы, по­сту­па­ю­щие из раз­лич­ных участ­ков кос­мо­са, при этом раз­лич­ные шумы пе­ре­во­дят­ся в по­сле­до­ва­тель­ность целых не­от­ри­ца­тель­ных чисел. Чисел может быть очень много, но не может быть мень­ше трёх. Все числа раз­лич­ны. Хотя бы одно из чисел нечётно.

В дан­ных, по­лу­чен­ных из од­но­го участ­ка, вы­де­ля­ет­ся ос­нов­ное под­мно­же­ство чисел. Это не­пу­стое под­мно­же­ство чисел (в него могут войти как одно число, так и все по­сту­пив­шие числа), такое, что их сумма чётна и мак­си­маль­на среди всех воз­мож­ных не­пу­стых под­мно­жеств с чётной сум­мой. Если таких под­мно­жеств не­сколь­ко, то из них вы­би­ра­ет­ся то под­мно­же­ство, ко­то­рое со­дер­жит наи­мень­шее ко­ли­че­ство эле­мен­тов.

Вам пред­ла­га­ет­ся на­пи­сать эф­фек­тив­ную, в том числе по ис­поль­зу­е­мой па­мя­ти, про­грам­му (ука­жи­те ис­поль­зу­е­мую вер­сию языка про­грам­ми­ро­ва­ния, на­при­мер, Borland Pascal 7.0), ко­то­рая будет об­ра­ба­ты­вать ре­зуль­та­ты, при­хо­дя­щие из од­но­го участ­ка, на­хо­дя ос­нов­ное под­мно­же­ство. Перед тек­стом про­грам­мы крат­ко опи­ши­те ис­поль­зу­е­мый Вами ал­го­ритм ре­ше­ния за­да­чи. На вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство сиг­на­лов N. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно целое не­от­ри­ца­тель­ное число, не пре­вы­ша­ю­щее 10⁹.

При­мер вход­ных дан­ных:

5

123

2

1000

0

10

Про­грам­ма долж­на вы­ве­сти в по­ряд­ке воз­рас­та­ния но­ме­ра сиг­на­лов, ко­то­рые при­над­ле­жат ос­нов­но­му под­мно­же­ству дан­но­го участ­ка. Ну­ме­ра­ция эле­мен­тов по­сле­до­ва­тель­но­сти ведётся с еди­ни­цы. При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных: 2 3 5.