In 30XX, due to the constant efforts of scientists and engineers, interaction among different planets becomes very active. Bitaro is a beaver who is working as an ambassador of an exchange program. His task is to introduce foods from the Earth to the habitants in different planets. He will leave for the JOI Planet at 1:00 in the afternoon.

Now, Bitaro is planning to introduce castella to the habitants in the JOI Planet. The castella was already cut into several pieces. Castella is a baked sponge cake made of flour, egg, sugar, and starch syrup.

The shape of the castella is a horizontally long rectangular box. It was cut into ~N~ pieces. The length of the ~i~-th piece ~(1 \le i \le N)~ from the left is an integer ~A_i~.

A couple of minutes ago, it turned out that the habitants in the JOI Planet do not like even integers. To cope with this problem, you will perform the following sequential operations until pieces of even length disappear.

1. Among the pieces of even length, you choose the rightmost one.
2. You cut the chosen piece into two pieces of equal length. Namely, if the length of the chosen piece is ~k~, you cut it into two pieces of length ~\frac{k}{2}~. You do not move the position of the pieces.

To confirm whether the operations are performed correctly, Bitaro will ask you ~Q~ questions. The ~j~-th question ~(1 \le j \le Q)~ is as follows.

• After all the operations are performed, what is the length of the ~X_j~-th piece from the left?

Given information of the castella and the questions, write a program which answers the questions.

Input Specification

Read the following data from the standard input. Given values are all integers.

~N~

~A_1~

~A_2~

~\vdots~

~A_N~

~Q~

~X_1~

~X_2~

~\vdots~

~X_Q~

Output Specification

Write ~Q~ lines to the standard output. The ~j~-th line ~(1 \le j \le Q)~ should contain the answer to the ~j~-th question.

Constraints

• ~1 \le N \le 200\,000~.
• ~1 \le A_i \le 1\,000\,000\,000~ ~(1 \le i \le N)~.
• ~1 \le Q \le 200\,000~.
• ~1 \le X_j \le 10^{15}~ ~(1 \le j \le Q)~.
• ~X_j \le X_{j+1}~ ~(1 \le j \le Q-1)~.
• After all the operations are performed, the castella is cut into at least ~X_Q~ pieces.

Subtasks

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

Sample Input 1

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

Sample Output 1

7
9
1
1
1
3

Explanation for Sample 1

In the beginning, the lengths of the pieces of the castella are ~14, 9, 8, 12~ from the left.

After all the operations are performed, the castella is cut into ~15~ pieces. The lengths of the pieces are ~7, 7, 9, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3~ from the left.

This sample input satisfies the constraints of Subtasks 2, 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

Explanation for Sample 2

This sample input satisfies the constraints of all the subtasks.

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

Explanation for Sample 3

This sample input satisfies the constraints of Subtasks 2, 3.