[AdditionalFile5642.zip](file://AdditionalFile5642.zip?type=additional_file)

#5642. 「PA 2014 Final」Bazarek

标签: 传统 | 时间限制: 11500 ms | 内存限制: 128 MiB |

题目描述

题目译自 PA 2014 Final Bazarek

Bajtek 在奶奶 Bajtula 家过暑假。每天早晨，奶奶都会去集市购买商品。小男孩很快发现了一个有趣的规律：每天奶奶在购物上花费的总额都是一个奇数。Bajtek 不久后确定，这一规律是所有 Bajtocka 奶奶们的共同特征。

每天，奶奶 Bajtula 在集市上的 $n$ 种商品中，每种最多购买一件。由于奶奶非常谨慎，她不想在购物时携带太多的现金。某天，她请 Bajtek 给她一个建议：如果她当天打算在集市上恰好购买 $k$ 件商品，她需要带多少钱。不幸的是，Bajtek 不知道奶奶打算买哪些具体商品，因此所带的金额必须足以支付任意 $k$ 件商品的组合（前提是它们的费用之和为奇数）。这种情况发生了好几次，于是 Bajtek 决定有系统地处理这个问题，编写一个程序，在已知集市上所有商品价格的情况下，回答奶奶的问题。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 1000000)$，表示集市上可供选择的商品数量。

第二行包含 $n$ 个范围在 $[1, 10^{9}]$ 之间的整数，表示每件商品的价格。

第三行包含一个整数 $m$ $(1 \leq m \leq 1000000)$，表示 Bajtek 还将在奶奶家度过的天数。

接下来的 $m$ 行，每行包含一个整数 $k_{i}$ $(1 \leq k_{i} \leq n)$，表示当天奶奶打算购买的商品数量。

输出格式

输出共 $m$ 行。在第 $i$ 行（对于 $i=1, \ldots, m$）中应包含一个整数，表示选择 $k_{i}$ 件商品所能达到的最大奇数总价。如果无法选出 $k_{i}$ 件商品使其总价为奇数，则输出 $-1$。

样例

输入

4
4 2 1 3
3
2
3
4

输出

7
9
-1