Bazarek

Limit pamięci: 128 MB

Mały Bajtek spędza wakacje u babci Bajtuli. Codziennie rano babcia idzie na bazarek, by zakupić pewne produkty. Chłopiec szybko zauważył ciekawą prawidłowość: każdego dnia babcia wydaje na zakupy kwotę wyrażającą się nieparzystą liczbą całkowitą. Bajtek wkrótce ustalił, iż dostrzeżona prawidłowość jest cechą charakterystyczną wszystkich bajtockich babć.

Każdego dnia babcia Bajtula kupuje po co najwyżej jednym egzemplarzu każdego z produktów dostępnych na bazarku. Babcia w swej zapobiegliwości nie chce brać na zakupy zbyt dużej sumy pieniędzy. Któregoś dnia poprosiła Bajtka o wskazówkę, ile pieniędzy musi ze sobą zabrać, jeśli tego dnia chce kupić na bazarku dokładnie produktów. Niestety Bajtek nie wie, które produkty babcia zamierza kupić, więc zabrana kwota musi wystarczyć na dowolne produktów (tak żeby suma ich kosztów była nieparzysta). Ta sama sytuacja powtórzyła się kilkukrotnie. Bajtek postanowił więc podejść do sprawy metodycznie i napisać program, który mając do dyspozycji ceny wszystkich produktów dostępnych na bazarku, będzie odpowiadał na pytania babci.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą () oznaczającą liczbę produktów dostępnych na bazarku. Drugi wiersz zawiera liczb całkowitych z zakresu , oznaczających ceny poszczególnych produktów. W trzecim wierszu znajduje się jedna liczba całkowita () oznaczająca liczbę dni, które Bajtek spędzi jeszcze u babci. Każdy z kolejnych wierszy zawiera jedną liczbę całkowitą (), oznaczającą liczbę produktów, które danego dnia zamierza kupić babcia.

Wyjście

Twój program powinien wypisać na wyjście wierszy. W -tym wierszu (dla ) powinna znaleźć się jedna liczba całkowita, oznaczająca maksymalną nieparzystą cenę produktów. Jeśli nie da się wybrać produktów, których łączna cena byłaby nieparzysta, w -tym wierszu wyjścia powinna znaleźć się liczba .

Przykład

Dla danych wejściowych:

4
4 2 1 3
3
2
3
4

poprawną odpowiedzią jest:

7
9
-1

Autor zadania: Jakub Radoszewski.