题目描述

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

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

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

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

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

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

输入格式

第一行一个整数 $N$。

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

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

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

输出格式

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

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

7
9
1
1
1
3

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

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\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$ 段。