本题需要文件读写

文件 IO 为：输入文件 split.in，输出文件 split.out。请使用上述文件名读入和输出。

题目描述

一条材料已经被切成了 $N$ 段，并按从左到右的顺序摆放。第 $i$ 段的长度为正整数 $A_i$。

接下来的加工要求每一段材料的长度都是奇数。只要仍有长度为偶数的段，就执行一次下面的操作：

1. 在所有长度为偶数的段中，选出最靠右的一段。
2. 把这一段从中间切开，得到两段长度相同的材料，并将它们放回原来这一段所在的位置。其他段的相对顺序不变。

例如，一段长度为 $6$ 的材料会被切成相邻的两段，每段长度均为 $3$。加工过程中只进行切分，不会把材料拼接起来，也不会改变已有各段的先后顺序。

所有操作结束后，质检员提出了 $Q$ 个查询。第 $j$ 个查询给出正整数 $X_j$，请你回答：此时从左到右第 $X_j$ 段材料的长度是多少？

保证查询位置按照不递减的顺序给出，而且每个查询位置都存在。位置编号从 $1$ 开始。

输入格式

第一行包含一个正整数 $T$，表示测试数据的组数。各组数据相互独立。

接下来依次给出 $T$ 组数据，每组格式如下：

• 第一行包含一个正整数 $N$。
• 接下来 $N$ 行，第 $i$ 行包含一个正整数 $A_i$。
• 接下来一行包含一个正整数 $Q$。
• 接下来 $Q$ 行，第 $j$ 行包含一个正整数 $X_j$。

输出格式

按输入顺序依次输出每组数据的答案。对于每组数据，输出 $Q$ 行，第 $j$ 行包含一个整数，表示该组第 $j$ 个查询的答案。组与组之间不需要输出额外标记。

样例输入 1

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$ 段，长度从左到右依次为：

因此，第 $2$ 段长为 $7$，第 $3$ 段长为 $9$，第 $5, 7, 11$ 段长均为 $1$，第 $13$ 段长为 $3$。

其它样例说明

• 样例 2：见选手目录下的 split/split2.in 与 split/split2.ans。该样例满足测试点 $1 \sim 5$ 的约束。
• 样例 3：见选手目录下的 split/split3.in 与 split/split3.ans。该样例满足测试点 $6 \sim 12$ 的约束。
• 样例 4：见选手目录下的 split/split4.in 与 split/split4.ans。该样例满足测试点 $13 \sim 20$ 的约束。
• 样例 5：见选手目录下的 split/split5.in 与 split/split5.ans。该样例满足测试点 $1 \sim 5$ 的约束。
• 样例 6：见选手目录下的 split/split6.in 与 split/split6.ans。该样例满足测试点 $13 \sim 20$ 的约束。

数据范围

对于所有数据，保证：

• $1 \le T \le 10$。
• 每组数据中，$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}$（$1 \le j < Q$），且操作全部结束后的段数不少于 $X_Q$。
• 同一输入文件中，所有数据的 $N$ 之和、$Q$ 之和分别不超过 $4 \times 10^5$。

各测试点的附加限制如下表所示：

点击下载大样例