Problem Description

It is the year $\mathrm{30XX}$. Due to the unremitting efforts of scientists and engineers, interplanetary exchanges have become increasingly frequent. Bitaro, a beaver, serves as an ambassador introducing Earth's food to extraterrestrials, and he is scheduled to depart for Planet JOI at 1 PM today.

One of the foods prepared to introduce to the JOI inhabitants is a sliced Castella cake. Castella is a sponge-like pastry made by adding egg, sugar, and maltose to wheat flour and baking it fluffy.

The Castella cake is in the shape of a long rectangular prism and is divided into $ N $ pieces along vertical cuts. The length of the $ i $th piece from the left ($1 \leq i \leq N$) is an integer $ A_i $.

Just recently, it was discovered that the JOI inhabitants have an aversion to even numbers. As a countermeasure, it was decided to repeatedly perform the following series of operations until there are no pieces with even lengths:

1. Select the rightmost piece with an even length.
2. Cut the selected piece vertically into two equal halves, i.e., if the length of the selected piece is $ k $, divide it into two pieces of length $\frac{k}{2}$ without changing their positions.

To check if the operations were performed correctly, Bitaro prepared $ Q $ questions. The $ j $th question ($1 \leq j \leq Q$) is as follows:

• What is the length of the piece located $ X_j $th from the left when all operations are completed?

Given the information about the Castella cake and the questions, create a program to find the answer to each question.

Input Format

The input is given from the standard input in the following format. All values are integers.

$ N $ $ A_1 $ $ A_2 $ $\vdots$ $ A_N $ $ Q $ $ X_1 $ $ X_2 $ $\vdots$ $ X_Q $

Output Format

Output $ Q $ lines to the standard output. The $ j $th line ($1 \leq j \leq Q$) should contain the answer to the $ j $th question.

Sample Input and Output

Sample Input #1

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

Sample Output #1

7
9
1
1
1
3

Sample Input #2

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

Sample Output #2

1
1
1
1
5
3
1
3

Sample Input #3

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

Sample Output #3

5
1
7
57
1

Notes/Hints

Constraints

• $1 \leq N \leq 200,000$.
• $1 \leq A_i \leq 1,000,000,000$ ($1 \leq i \leq N$).
• $1 \leq Q \leq 200,000$.
• $1 \leq X_j \leq 1,000,000,000,000,000 (= 10^{15})$ ($1 \leq j \leq Q$).
• $X_j \leq X_{j + 1}$ ($1 \leq j \leq Q - 1$).
• When all operations are completed, the Castella cake is divided into at least $ X_Q $ pieces.

Subtasks

1. ($ 25 $ points) $A_i \leq 8$ ($1 \leq i \leq N$).
2. ($ 35 $ points) $N \leq 1,000$, $Q \leq 1,000$.
3. ($ 40 $ points) No additional constraints.

Sample Explanation 1

Initially, the lengths of the pieces of the Castella cake are $ 14, 9, 8, 12 $ from left to right. After all operations are completed, the cake is divided into $ 15 $ pieces, and the lengths of the pieces are $ 7, 7, 9, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3 $ from left to right. This input-output example satisfies the constraints of Subtasks $ 2 $ and $ 3 $.

Sample Explanation 2

This input-output example satisfies the constraints of all subtasks.

Sample Explanation 3

This input-output example satisfies the constraints of Subtasks $ 2 $ and $ 3 $.

见题面 Input 部分

见题面 Output 部分