该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

图灵有一台时光机，2070年，图灵要在纽约建一个分校，所以2070年的朱爷爷穿越到2024年问昔日的好友小博老师借一些木材。 小博老师有$n$段木材，但是朱需要一些长度为奇数的木材，所以小博老师需要将这些木材进行处理： 1.选择最左边长度为偶数的木材； 2.将这段长度为$l$的木材将其从中间锯开，变为$l/2$。 朱老师觉得小博老师不靠谱，所以他会给出$Q$次查询，询问经过处理后，第$q_i$段木材的长度。（朱老师的查询位置时递增的）

输入格式

第一行，一个正整数 $N$。

接下来 $N$ 行，第 $i$ 行一个正整数 $A_i$。表示处理前第$i$段木材的长度为$A_i$。

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

接下来 $Q$ 行，第 $j$ 行一个正整数 $q_j$。

输出格式

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

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

提示

【样例解释 #1】

一开始，从左到右的段木材的长度分别为 $14, 9, 8, 12$。

当所有操作执行完毕后，所有木材总共被切成了 $15$ 段。从左到右的段的长度分别为 $7, 7, 9, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3$。

这个样例满足子任务 $2, 3$ 的限制。

【样例解释 #2】

这个样例满足所有子任务的限制。

【样例解释 #3】

这个样例满足子任务 $2, 3$ 的限制。

【数据范围】

本题采用捆绑测试。

对于 $100 \%$ 的数据，$1 \le N, Q \le 2 \times {10}^5$，$1 \le A_i \le {10}^9$，$1 \le q_j \le {10}^{15}$，$q_j \le q_{j + 1}$，保证当所有操作执行完毕后，木材被切成了至少 $q_Q$ 段。

• 子任务 $1$（$25$ 分）：$A_i \le 8$。
• 子任务 $2$（$35$ 分）：$N, Q \le 1000$。
• 子任务 $3$（$40$ 分）：无特殊限制。