問題文

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

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

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

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

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

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

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

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

制約

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

小課題

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

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