Little Bajtek is spending his holidays at Grandma Bajtula’s house. Every morning, Grandma goes to the market to buy some products. Bajtek quickly noticed an interesting pattern: each day, Grandma spends an amount of money that is an odd integer. He soon realized this pattern is a characteristic trait of all Bajtocian grandmothers.

Each day, Grandma Bajtula buys at most one of each of the available $n$ products at the market. Being careful and thrifty, she doesn’t want to take more money with her than necessary. One day, she asked Bajtek for advice on how much money she should bring if she wants to buy exactly $k$ products that day. Unfortunately, Bajtek doesn’t know which products she intends to buy, so the amount of money she takes must be enough to cover any $k$ products whose total cost is odd. This situation repeats over several days. Bajtek decides to tackle the problem methodically and write a program that, given the prices of all products available at the market, will answer Grandma’s questions.

Input

The first line contains one integer $n$ ($1 \leq n \leq 1,000,000$), the number of products available at the market.

The second line contains $n$ integers in non-decreasing order, each in the range $[1,10^9]$, representing the prices of the products.

The third line contains one integer $m$ ($1 \leq m \leq 1,000,000$), the number of days Bajtek will still spend at Grandma’s.

Each of the next $m$ lines contains one integer $k\_i$ ($1 \leq k\_i \leq n$), representing how many products Grandma wants to buy on day $i$.

Output

Your program should output $m$ lines. In the $i$-th line (for $i=1,\dots,m$), print one integer: the maximum possible odd total cost of any $k_i$ products. If it’s not possible to choose $k_i$ products with an odd total cost, print -1.

Example

For the input:

4
1 2 3 4
3
2
3
4

The correct output is:

7
9
-1

小比特正在奶奶巴图拉家度假。每天早上奶奶都会去市场购买一些产品。小男孩很快发现了一个有趣的规律：奶奶每天花在购物上的金额都是一个奇数整数。比特很快确定，这个规律是所有比特奶奶的共同特征。

每天，巴图拉奶奶在市场上的 $n$ 种产品中，每种最多购买一件。奶奶很节俭，不想带太多钱去购物。有一天，她问比特，如果她那天想在市场上购买正好 $k$ 种产品，她需要带多少钱。不幸的是，比特不知道奶奶打算买哪些产品，所以她带的钱必须足够购买任意 $k$ 种产品（以便它们总价格是奇数）。同样的情况重复发生了好几次。因此，比特决定系统地解决这个问题，编写一个程序，利用市场上所有产品的价格，来回答奶奶的问题。

输入

输入的第一行包含一个整数 $n$ ( $1 \le n \le 1,000,000$ )，表示市场上可用产品的数量。第二行包含 $n$ 个整数，范围在 $[1,10^9]$ 之间，表示各个产品的价格。这些数字以非递减顺序给出。

第三行包含一个整数 $m$ ( $1 \le m \le 1,000,000$ )，表示比特将与奶奶一起度过的剩余天数。接下来的 $m$ 行，每行包含一个整数 $k_i$ ( $1 \le k\_i \le n$ )，表示奶奶当天打算购买的产品数量。

输出

你的程序应该输出 $m$ 行。第 $i$ 行（对于 $i=1,\ldots,m$ ）应该包含一个整数，表示 $k_i$ 种产品的最大奇数价格。如果无法选择 $k_i$ 种产品使总价格为奇数，则第 $i$ 行输出应为 $ -1 $。

示例

对于以下输入数据：

4
1 2 3 4
3
2
3
4

正确的输出是：

7
9
-1