切蛋糕

题目描述:

狐狸尼克新开了一家蛋糕店，为了促销活动，特意邀请兔警官朱迪来切蛋糕，分享给食客们品尝。

狐狸尼克制作的蛋糕形状是一个在水平方向上很长的长方体。蛋糕已经被狐狸尼克切成了 N 段，其中从左往右的第 i 段的长度为正整数 Ai。

食客们已经排起了队伍等待兔警官朱迪为她们切蛋糕。由于食客们都 不喜欢偶数 长度的蛋糕。为了解决此问题，朱迪需要 不断地 执行下列操作，直到 不存在长度为偶数 的蛋糕。

▲ 在长度为偶数的段中，朱迪选择 最靠右 的一段。

▲ 朱迪将选中的这一段切成两个长度相等的蛋糕段。也就是说，假设选中的这一段的长度是 L，朱迪将其切成长度为 L/2 的两段蛋糕。朱迪不改变其它蛋糕的位置。

为了确认操作是否被正确地执行了，食客们让狐狸尼克回答 Q 个询问。第 j 个询问如下：
当所有操作被朱迪执行完毕后，从左往右的第 Xj 段蛋糕的长度为多少？ 

输入格式:

第一行一个正整数 N。

接下来 N 行，第 i 行一个正整数 Ai。

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

接下来 Q 行，第 j 行一个正整数 Xj。保证当所有操作执行完毕后，蛋糕被切成了至少 XQ 段。
( 数据保证序列 Xj 单调不降  )。 

输出格式:

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

数据范围:

对于100%的数据：1 ≤ N, Q ≤ 2×105；1 ≤ Ai ≤ 109；1 ≤ Xj ≤ 1015；Xj ≤ Xj+1 ( 1 ≤ j < Q  )。

测试编号 特殊性质
1 如果Ai 为偶数，则Ai = 2k ( 1 ≤ k < 30 ) 
2~3 Ai ≤ 8
4~6 N, Q ≤ 103
7~10 没有额外限制

样例输入:

样例1：
4
14
9
8
12
6
2
3
5
7
11
13

样例2：
16
536870912
402653184
536870912
536870912
134217728
536870912
671088640
536870912
536870912
536870912
939524096
805306368
536870912
956301312
536870912
536870912
5
2500000000
3355443201
4294967296
5111111111
6190792704

样例输出:

样例1：
7
9
1
1
1
3

样例2：
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。 

时间限制: 1000ms
空间限制: 256MB

来源: 温州市计算机学会2023比赛