시장 장보기

바이트 마을의 할머니는 매일 아침 시장에 가서 장을 본다. 손자는 할머니가 장을 볼 때마다 내는 금액이 언제나 홀수라는 규칙을 발견했고, 이것이 바이트 마을 할머니의 공통된 습관이라는 사실도 알아냈다.

시장에는 물건 $n$개가 있고, 할머니는 각 물건을 최대 한 개까지만 산다. 할머니는 필요한 것보다 많은 돈을 들고 나가고 싶어 하지 않는다. 어느 날 할머니는 그날 물건을 정확히 $k$개 살 예정인데 돈을 얼마나 가져가야 하는지 손자에게 물었다. 손자는 할머니가 어떤 물건을 고를지 모르므로, 가져가는 금액은 가격의 합이 홀수가 되는 $k$개짜리 조합 중 어느 것에도 모자라지 않아야 한다.

정리하면, 물건 $n$개 중에서 정확히 $k$개를 골라 가격의 합을 홀수로 만들 때 그 합의 최댓값을 구하면 된다. 같은 질문이 여러 날 반복되므로, 손자는 모든 물건의 가격을 한 번 읽어 두고 할머니의 질문마다 답하는 프로그램을 짜기로 했다.

첫째 줄에 시장에 있는 물건의 개수 $n$ ($1 \le n \le 10^6$)이 주어진다. 둘째 줄에 물건 $n$개의 가격이 공백으로 구분되어 주어지며, 각 가격은 $1$ 이상 $10^9$ 이하의 정수이다. 셋째 줄에 손자가 할머니 집에서 더 보낼 날의 수 $m$ ($1 \le m \le 10^6$)이 주어진다. 이어지는 $m$개의 줄에는 그날 할머니가 사려는 물건의 개수 $k_i$ ($1 \le k_i \le n$)가 한 줄에 하나씩 주어진다.

$m$개의 줄을 출력한다. $i$번째 줄에는 물건을 정확히 $k_i$개 골랐을 때 가격의 합이 홀수가 되는 경우 중 가장 큰 합을 출력한다. 가격의 합이 홀수가 되도록 $k_i$개를 고를 수 없으면 -1을 출력한다.