문제

時は30XX 年．科学者・技術者のたゆまぬ努力により，異星間の交流が盛んに行われるようになっていた．ビーバーのビ太郎は異星人に地球の食べ物を紹介するアンバサダーを務めており，今日の午後1 時にJOI 星へ向けて出発する予定である．

今回JOI 星人に紹介する食べ物のひとつとして，切り分けたカステラが用意されている．カステラは小麦粉に鶏卵・砂糖・水あめを加え，スポンジ状にふっくらと焼いた菓子である．

カステラは横長の直方体の形をしており，縦方向の切れ目に沿って $N$ 個のピースに分割されている．左から $i$ 番目 ($1 \le i \le N$) のピースの長さは整数 $A_i$ である．

つい先ほど，JOI 星人は偶数に嫌悪感を示すということが判明した．そこで対処として，長さが偶数のピースが無くなるまで以下の一連の操作を繰り返すことにした．

1. 長さが偶数のピースのうち最も右にあるものを選ぶ．
2. 選んだピースを縦方向に切って2 等分する．すなわち，選んだピースの長さを $k$ としたとき，そのピースを位置を変えずに長さ $\frac{k}{2}$ のピース2 つに分割する．

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

• すべての操作が終了したとき，左から $X_j$ 番目にあるピースの長さは何であるか．

カステラと質問の情報が与えられたとき，各質問の答えを求めるプログラムを作成せよ．

입력

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

$N$
$A_1$
$A_2$
$\ldots$
$A_N$
$Q$
$X_1$
$X_2$
$\ldots$
$X_Q$

출력

標準出力に $Q$ 行出力せよ． $j$ 行目 ($1 \le j \le Q$) には， $j$ 番目の質問の答えを出力せよ．

예제 입력 1

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

예제 출력 1

7
9
1
1
1
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

제한

• $1 \le N \le 200\,000$．
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le N$)．
• $1 \le Q \le 200\,000$．
• $1 \le X_j \le 1\,000\,000\,000\,000\,000$ ($= 10^{15}$) ($1 \le j \le Q$)．
• $X_j \le X_{j+1}$ ($1 \le j \le Q - 1$)．
• すべての操作が終了したとき，カステラは $X_Q$ 個以上のピースに分割されている．

서브태스크

1. ($25$ 점) $A_i \le 8$ ($1 \le i \le N$)．
2. ($35$ 점) $N \le 1\,000$, $Q \le 1\,000$．
3. ($40$ 점) 追加の制約はない．