1548 - インターカステラー(Intercastellar)

問題

時は 30XX 年。
科学者・技術者のたゆまぬ努力により、異星間の交流が盛んに行われるようになってい た。
ビーバーのビ太郎は異星人に地球の食べ物を紹介するアンバサダーを務めており、今日の午後1時にJOI星へ向けて出発する予定である。
今回JOI星人に紹介する食べ物のひとつとして、切り分けたカステラが用意されている。
カステラは小麦粉に鶏卵・砂糖・水あめを加え、スポンジ状にふっくらと焼いた菓子である。
カステラは横長の直方体の形をしており、縦方向の切れ目に沿ってN個のピースに分割されている。左からi番目(1 ≦ i ≦ N)のピースの長さは整数Aiである。
つい先ほど、JOI星人は偶数に嫌悪感を示すということが判明した。
そこで対処として、長さが偶数のピースが無くなるまで以下の一連の操作を繰り返すことにした。

1. 長さが偶数のピースのうち最も右にあるものを選ぶ。

2. 選んだピースを縦方向に切って2等分する。すなわち，選んだピースの長さをkとしたとき、そのピースを位置を変えずに長さk2のピース 2 つに分割する。

操作が正しく行われたかチェックするため、ビ太郎は Q 個の質問を準備しておいた。
j 番目(1 ≦ j ≦ Q)の質問は以下の通りである。

• すべての操作が終了したとき、左から Xj 番目にあるピースの長さは何であるか。
カステラと質問の情報が与えられたとき、各質問の答えを求めるプログラムを作成せよ。

入力

入力は以下の形式で標準入力から与えられる。入力される値はすべて整数である。

N
A1
A2
.
.
.
AN
Q
X1
X2
.
.
.
XQ

出力

標準出力にQ行出力せよ。j行目(1 ≦ j ≦ Q)には、j番目の質問の答えを出力せよ。

制約

• 1 ≦ N ≦ 200 000．
• 1 ≦ Ai ≦ 1 000 000 000 (1 ≦ i ≦ N)．
• 1 ≦ Q ≦ 200 000．
• 1 ≦ Xj ≦ 1 000 000 000 000 000 (= 1015) (1 ≦ j ≦ Q)．
• Xj ≦ Xj+1 (1 ≦ j ≦ Q − 1)．
• すべての操作が終了したとき，カステラは XQ 個以上のピースに分割されている．

• $0 \leq X, Y \leq 10^{1000000}$

入出力例

入力例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の制約を満たす。