切蛋糕

题目描述

狐狸尼克做了一个很长的长方体蛋糕，并把它从左到右切成了 $N$ 段，第 $i$ 段的长度为正整数 $A_i$。由于食客们都不喜欢偶数长度的蛋糕，兔警官朱迪需要不断执行以下操作，直到不存在偶数长度的蛋糕段为止：

• 在所有长度为偶数的蛋糕段中，选择最靠右的一段。
• 设其长度为 $L$，则将它切成两段长度都为 $L/2$ 的蛋糕段，并保持其他蛋糕段相对顺序不变。

现在有 $Q$ 次询问。对于每个询问给定一个位置 $X_j$，你需要回答：当所有切分操作全部结束后，从左到右数第 $X_j$ 段蛋糕的长度是多少。

数据范围

• $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}$

输入格式

从标准输入按以下格式读取数据：

$N$

$A_1$

$A_2$

$\vdots$

$A_N$

$Q$

$X_1$

$X_2$

$\vdots$

$X_Q$

其中：

• 第一行输入一个正整数 $N$。
• 接下来 $N$ 行，第 $i$ 行输入一个正整数 $A_i$，表示第 $i$ 段蛋糕的初始长度。
• 接下来一行输入一个正整数 $Q$。
• 再接下来 $Q$ 行，第 $j$ 行输入一个正整数 $X_j$，并保证最终蛋糕段数至少为 $X_Q$。

输出格式

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

样例

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

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