在 30XX 年，由于科学家和工程师们的不懈努力，不同行星之间的交流变得非常活跃。Bitaro 是一只海狸，他担任着交换项目的形象大使。他的任务是向不同行星的居民介绍来自地球的食物。他将于下午 1:00 出发前往 JOI 行星。

现在，Bitaro 计划向 JOI 行星的居民介绍长崎蛋糕（castella）。长崎蛋糕已经被切成了若干块。长崎蛋糕是一种由面粉、鸡蛋、糖和淀粉糖浆制成的烘焙海绵蛋糕。

长崎蛋糕的形状是一个水平放置的长方体。它被切成了 $N$ 块。从左往右数第 $i$ 块（$1 \le i \le N$）的长度是一个整数 $A_i$。

几分钟前，人们发现 JOI 行星的居民不喜欢偶数。为了解决这个问题，你需要执行以下顺序操作，直到所有偶数长度的块都消失为止：

1. 在所有偶数长度的块中，选择最右边的一块。
2. 将选中的块切成两块等长的块。也就是说，如果选中的块长度为 $k$，则将其切成两块长度为 $\frac{k}{2}$ 的块。你不能改变这些块的位置。

为了确认操作是否正确执行，Bitaro 会问你 $Q$ 个问题。第 $j$ 个问题（$1 \le j \le Q$）如下：

• 在所有操作完成后，从左往右数第 $X_j$ 块的长度是多少？

给定长崎蛋糕的信息和这些问题，请编写一个程序来回答这些问题。

输入格式

从标准输入读取以下数据。所有给定的值均为整数。

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

输出格式

向标准输出写入 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）应包含第 $j$ 个问题的答案。

数据范围

• $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 1\,000\,000\,000\,000\,000$ ($= 10^{15}$) ($1 \le j \le Q$)
• $X_j \le X_{j+1}$ ($1 \le j \le Q - 1$)
• 在所有操作完成后，长崎蛋糕被切成了至少 $X_Q$ 块。

子任务

1. (25 分) $A_i \le 8$ ($1 \le i \le N$)
2. (35 分) $N \le 1\,000, Q \le 1\,000$
3. (40 分) 无附加限制

样例

样例输入 1

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

样例输出 1

7
9
1
1
1
3

说明 1

最初，从左往右数，长崎蛋糕各块的长度为 14, 9, 8, 12。 在所有操作完成后，长崎蛋糕被切成了 15 块。从左往右数，各块的长度为 7, 7, 9, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3。 该样例输入满足子任务 2 和 3 的限制。

样例输入 2

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

样例输出 2

1
1
1
1
5
3
1
3

说明 2

该样例输入满足所有子任务的限制。

样例输入 3

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

样例输出 3

5
1
7
57
1

说明 3

该样例输入满足子任务 2 和 3 的限制。