시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 256 MB 1 1 1 100.000%

문제

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 n 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 k produktów. Niestety Bajtek nie wie, które produkty babcia zamierza kupić, więc zabrana kwota musi wystarczyć na dowolne k 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.

입력

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

출력

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

예제 입력 1

4
4 2 1 3
3
2
3
4

예제 출력 1

7
9
-1