题目描述:

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

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

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

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

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

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

输入格式:

第一行一个正整数 N。

接下来 N 行，第 i 行一个正整数 $A​_i$​。

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

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

输出格式:

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

数据范围:

对于100%的数据：$1 ≤ N, Q ≤ 2×10​^5​；1 ≤ A​_i ​≤ 10​^9​；1 ≤ X​_j ​≤ 10​^{15}​；X​_j ≤ X_{j+1} ( 1 ≤ j < Q )$。

样例输入:

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