题目描述

蛋糕的形状是一个在水平方向上很长的长方体。它被切成了 $N$ 段，其中从左往右的第 $i$ 段的长度为整数 $A_i$。

几分钟前，我们得知星球的居民不喜欢偶数。为了解决此问题，你需要不断执行下列操作，直到不存在长度为偶数的段。

1. 在长度为偶数的段中，你选择最靠右的一段。
2. 你将选中的这一段切成两个长度相等的段。也就是说，假设选中的这一段的长度是 $k$，你将其切成长度为 $\frac{k}{2}$ 的两段。你不改变其他段的位置。

为了确认操作是否被正确地执行了，比太郎让你回答 $Q$ 个询问。第 $j$ 个询问如下：

• 当所有操作执行完毕后，从左往右的第 $X_j$ 段的长度为多少？

给定蛋糕的信息与询问，请写一个程序回答所有询问。

输入格式

第一行包含一个正整数 $N$。

接下来 $N$ 行，第 $i$ 行包含一个正整数 $A_i$。

接下来一行包含一个正整数 $Q$。

接下来 $Q$ 行，第 $j$ 行包含一个正整数 $X_j$。

输出格式

输出 $Q$ 行，第 $j$ 行一个数，表示第 $j$ 个询问的答案。

样例输入 1

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

样例输出 1

7
9
1
1
1
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

样例输入 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

说明

样例解释

对于样例 $1$，一开始，蛋糕从左到右的段的长度分别为 $14, 9, 8, 12$。 当所有操作执行完毕后，蛋糕切成了 $15$ 段。从左到右的段的长度分别为 $7, 7, 9, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3$。 该样例满足子任务 $2, 3$ 的限制。对于样例 $3$，也满足子任务 $2, 3$ 的限制。

其它样例说明

• 样例 4：见选手目录下的 cake/cake4.in 与 cake/cake4.ans，该测试用例满足测试点 $13 \sim 20$ 的约束条件。

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据：

• $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}$
• 保证当所有操作执行完毕后，蛋糕被切成了至少 $X_Q$ 段。

各子任务的附加限制如下表所示：

点击下载大样例