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

[problemUrl]: https://atcoder.jp/contests/joi2022ho/tasks/joi2022ho_a 時は $ \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 $ 点) 追加の制約はない． - - - - - - ### Sample Explanation 1 はじめ，カステラの各ピースの長さは左から順に $ 14,\ 9,\ 8,\ 12 $ である． 一連の操作が終了したとき，カステラは $ 15 $ 個のピースに分割されており，各ピースの長さは左から順に $ 7,\ 7,\ 9,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 1,\ 3,\ 3,\ 3,\ 3 $ となる． この入出力例は小課題 $ 2,\ 3 $ の制約を満たす． - - - - - - ### Sample Explanation 2 この入出力例はすべての小課題の制約を満たす． - - - - - - ### Sample Explanation 3 この入出力例は小課題 $ 2,\ 3 $ の制約を満たす．