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

時は30XX 年.科学者・技術者のたゆまぬ努力により,異星間の交流が盛んに行われるようになってい
た.ビーバーのビ太郎は異星人に地球の食べ物を紹介するアンバサダーを務めており,今日の午後1 時に
JOI 星へ向けて出発する予定である.
今回JOI 星人に紹介する食べ物のひとつとして,切り分けたカステラが用意されている.カステラは小麦
粉に鶏卵・砂糖・水あめを加え,スポンジ状にふっくらと焼いた菓子である.
カステラは横長の直方体の形をしており,縦方向の切れ目に沿ってN 個のピースに分割されている.左
からi 番目(1 ≦i ≦N) のピースの長さは整数Ai である.
つい先ほど,JOI 星人は偶数に嫌悪感を示すということが判明した.そこで対処として,長さが偶数の
ピースが無くなるまで以下の一連の操作を繰り返すことにした.
1. 長さが偶数のピースのうち最も右にあるものを選ぶ.
2. 選んだピースを縦方向に切って2 等分する.すなわち,選んだピースの長さをk としたとき,その
ピースを位置を変えずに長さk
2 のピース2 つに分割する.
操作が正しく行われたかチェックするため,ビ太郎はQ 個の質問を準備しておいた.j 番目(1 ≦j ≦Q)
の質問は以下の通りである.
• すべての操作が終了したとき,左からX j 番目にあるピースの長さは何であるか.
カステラと質問の情報が与えられたとき,各質問の答えを求めるプログラムを作成せよ.

第21 回日本情報オリンピック(JOI 2021/2022) 本選
2022 年2 月13 日(オンライン開催)

• 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 個以上のピースに分割されている.

1. (25 点) Ai ≦8 (1 ≦i ≦N).
2. (35 点) N ≦1 000,Q ≦1 000.
3. (40 点) 追加の制約はない.

第21 回日本情報オリンピック(JOI 2021/2022) 本選
2022 年2 月13 日(オンライン開催)

入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N
A1
A2
...
AN
Q
X1
X2
...
XQ

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

생성자가 기록되지 않았습니다.

출처 JOI 2022 Final