配点: 100 点
問題文
时间是 \mathrm{30XX} 年。在科学家和工程师的不懈努力下,不同星球之间的交流变得更加普遍。海狸 Bitaro 正在担任向外星人介绍地球食物的大使,并计划于今天下午 1 点出发前往 JOI 星球。
这次我们要向JOI Alien介绍的食物之一是切碎的卡斯提拉。 Castella 是一种柔软的海绵状糖果,是在小麦粉中添加鸡蛋、糖和淀粉糖浆制成的。
卡斯特拉的形状像一个水平长的长方体,并且卡斯特拉的形状像一个长方体。 它被分为 N 块。从左边开始 i 番目 (1 \leqq i \leqq N) 片段长度为整数 A_i 。
最近发现JOI外星人表现出对偶数的厌恶。作为解决方法,我决定重复以下一系列操作,直到没有长度均匀的片段为止。
- 选择最右边的长度相等的片段。
- 纵向剪切选定的部分。 2 分成相等的部分。换句话说,所选片段的长度是 k ,我们可以改变片段的长度而不改变它的位置。 \displaystyle\frac{k}{2} 片 分为 2 。
为了检查操作是否正确执行,Bitaro 我已经准备了 Q 问题。j 番目 (1 \leqq j \leqq Q) 的问题如下。
- 当所有操作完成后,从左开始 第 X_j 块的长度是多少?
给定城堡和问题信息,编写一个程序来查找每个问题的答案。

入力
输入是按以下格式从标准输入给出的。所有输入值都是整数。
N A_1 A_2 \vdots A_N Q X_1 X_2 \vdots X_Q
出力
到标准输出 输出 Q 行。j 行目 (1 \leqq j \leqq Q)有 打印第j 问题的答案。
制約
- 1 \leqq N \leqq 200\,000.
- 1 \leqq A_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
- 1 \leqq Q \leqq 200\,000.
- 1 \leqq X_j \leqq 1\,000\,000\,000\,000\,000\ (= 10^{15}) (1 \leqq j \leqq Q).
- X_{j} \leqq X_{j + 1} (1 \leqq j \leqq Q - 1).
- 当所有操作完成后,Castella 它被分成 X_Q 或更多块。
小課題
- (25 点) A_i \leqq 8 (1 \leqq i \leqq N).
- (35 点) N \leqq 1\,000,Q \leqq 1\,000.
- (40 点)没有额外的限制。
入力例 1
4 14 9 8 12 6 2 3 5 7 11 13
出力例 1
7 9 1 1 1 3
最初,每块卡斯特拉的长度是从左边开始的。 14, 9, 8, 12 。
当这一系列操作完成后,卡斯特拉 它被分成 15 块,每块的长度从左开始按顺序显示。 7, 7, 9, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3 变为。
这个输入/输出示例是一个小任务。 2, 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
这个输入/输出示例是一个小任务。 2, 3 满足约束。