Little Bytec spends his holidays at Grandma Bytegranny. Every morning Grandma goes to the little marketplace to buy various products. The boy quickly noticed an interesting regularity: every day his grandmother spends an amount expressed by an odd integer on her shopping. Bytec soon found out that this regularity is characteristic to all Byteonian grandmothers.
Every day Bytegranny buys not more than one item of each of the $n$ products available in the market. Thrifty grandma does not want to do her shopping carrying too much money with her. One day she asked Bytec for a hint of how much money she needs to take, in case she wants to purchase exactly $k$ products. Unfortunately, Bytec does not know which products grandmother wants to buy, so the amount taken must be sufficient for any $k$ items (and that their total cost would be an odd number). The same situation repeated itself several times. Bytec then decided to approach the problem methodically and write a program that, provided all the prices of products available on the market, will answer grandmother's questions.
Input
The first line of input contains one integer $n$ ($1 \le n \le 1\,000\,000$) denoting the number of products available at the market. The second line contains $n$ integers from the range $[1,10^9]$, denoting the prices of individual products. The third line contains one integer $m$ ($1 \le m \le 1\,000\,000$) denoting the remaining number of days that Bytec will stay at Grandma's place. Each of the following $m$ lines contains one integer $k_i$ ($1 \le k_i \le n$), denoting the number of products that grandma is going to buy on a given day.
Output
Your program should output $m$ lines. In the $i$-th line (for $i=1,\ldots,m$) one integer should be written, indicating the maximum odd price total for $k_i$ products. In case it is not possible to determine $k_i$ products, such that their total price would be represented by an odd number, the $i$-th output line should contain the number $-1$.
Example
Input
4 1 2 3 4 3 2 3 4
Output
7 9 -1