题目描述

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

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

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

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

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

输入格式

第一行一个整数 $N$。

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

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

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

输出格式

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

输入输出样例 #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$ 这样的几段。

在你做完操作之后，蛋糕被切成了 $7,7,9,1,1,1,1,1,1,1,1,3,3,3,3$ 这样的几段。

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

输入输出样例 #2

输入 #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

输入 #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

数据范围

对于全部数据，保证 $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$ 段。