题目描述

译自 JOI 2022 Final T1「インターカステラー / Intercastellar」

河狸 Bitaro 是一名来自地球的蛋糕推销员，这天他来到了 JOI 星。

蛋糕已经被切成了 $N$ 段，第 $i$ 段长 $A_i$，用作推销。

但是在推销开始前，Bitaro 得知到 JOI 星的居民们不喜欢偶数，为了更好的营销，他决定去掉所有的偶数长度的段。所以他希望助手，也就是你，来解决这个问题。

你决定，每次选择最右边的长度为偶数的蛋糕，将它对半切开，并放回原处。

为了证明你真的解决了这个问题，Bitaro 会问你解决问题后第 $X_i$ 段蛋糕的长度。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，一行一个整数 $A_i$。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，一行一个整数 $X_i$ 表示询问第 $X_i$ 段蛋糕的长度。

输出格式

输出 $Q$ 行，一行一个整数，表示你对于每一组询问的回答。

样例 1

输入

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

输出

7
9
1
1
1
3

解释
一开始的时候蛋糕被切成了 $14,9,8,12$ 这样的几段。

在你做完操作之后，蛋糕被切成了 $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

输出

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

输出

5
1
7
57
1

这个样例满足子任务 $2,3$ 的限制。

数据范围

对于全部数据，保证：

• $1 \le N, Q \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le X_i \le 10^{15}$
• $X_i$ 单调不降
• 在最后蛋糕被切成的段数至少 $X_Q$ 段

子任务	特殊限制	分数
1	$A_i \le 8$	25
2	$N, Q \le 10^3$	35
3	无特殊限制	40