Background

In the year 30XX, thanks to the continuous efforts of scientists and engineers, interactions between different planets have become very active. Bitaro is a beaver, and he is now an ambassador of an exchange program. His task is to introduce foods from Earth to the residents of different planets. He will depart at 1 p.m. for the JOI planet.

Now, Bitaro is planning to introduce castella to the residents of the JOI planet. The castella has already been cut into several pieces. Castella is a baked sponge cake made from flour, eggs, sugar, and starch syrup.

Problem Description

The castella has the shape of a very long rectangular prism in the horizontal direction. It is cut into $N$ pieces, where the length of the $i$-th piece from left to right is an integer $A_i$.

A few minutes ago, we learned that the residents of the JOI planet do not like even numbers. To solve this problem, you need to repeatedly perform the following operation until there is no piece with an even length.

1. Among the pieces with even length, choose the rightmost one.
2. Cut the chosen piece into two pieces of equal length. That is, if the length of the chosen piece is $k$, cut it into two pieces of length $\displaystyle \frac{k}{2}$. You do not change the positions of the other pieces.

To confirm whether the operations are carried out correctly, Bitaro asks you to answer $Q$ queries. The $j$-th query is as follows:

• After all operations are finished, what is the length of the $X_j$-th piece from left to right?

Given the information of the castella and the queries, write a program to answer all queries.

Input Format

The first line contains a positive integer $N$.

The next $N$ lines each contain a positive integer $A_i$ on the $i$-th line.

The next line contains a positive integer $Q$.

The next $Q$ lines each contain a positive integer $X_j$ on the $j$-th line.

Output Format

Output $Q$ lines. On the $j$-th line, output one number, which is the answer to the $j$-th query.

4
14
9
8
12
6
2
3
5
7
11
13

7
9
1
1
1
3

13
1
4
1
4
2
1
3
5
6
2
3
7
3
8
2
10
11
13
15
17
18
20

1
1
1
1
5
3
1
3

16
536870912
402653184
536870912
536870912
134217728
536870912
671088640
536870912
536870912
536870912
939524096
805306368
536870912
956301312
536870912
536870912
5
2500000000
3355443201
4294967296
5111111111
6190792704

5
1
7
57
1

Hint

[Sample Explanation #1]

At the beginning, from left to right, the lengths of the pieces of castella are $14, 9, 8, 12$.

After all operations are finished, the castella is cut into $15$ pieces. From left to right, the lengths are $7, 7, 9, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3$.

This sample satisfies the constraints of subtasks $2$ and $3$.

[Sample Explanation #2]

This sample satisfies the constraints of all subtasks.

[Sample Explanation #3]

This sample satisfies the constraints of subtasks $2$ and $3$.

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le N, Q \le 2 \times {10}^5$, $1 \le A_i \le {10}^9$, $1 \le X_j \le {10}^{15}$, $X_j \le X_{j + 1}$, and it is guaranteed that after all operations are finished, the castella is cut into at least $X_Q$ pieces.

• Subtask $1$ ($25$ points): $A_i \le 8$.
• Subtask $2$ ($35$ points): $N, Q \le 1000$.
• Subtask $3$ ($40$ points): No additional constraints.

Translated from JOI 2022 Final T1 「インターカステラー / Intercastellar」

Translated by ChatGPT 5