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

時は \(\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\) 番目にあるピースの長さは何であるか．

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

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

\(N\)
\(A_1\)
\(A_2\)
\(\vdots\)
\(A_N\)
\(Q\)
\(X_1\)
\(X_2\)
\(\vdots\)
\(X_Q\)

標準出力に \(Q\) 行出力せよ．\(j\) 行目 (\(1 \leqq j \leqq Q\)) には，\(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\) 点) 追加の制約はない．

JOI 2022 · JCIOI · CC BY-SA 4.0