레이팅 미적용時は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 個以上のピースに分割されている.
- (25 点) Ai ≦8 (1 ≦i ≦N).
- (35 点) N ≦1 000,Q ≦1 000.
- (40 点) 追加の制約はない.
第21 回日本情報オリンピック(JOI 2021/2022) 本選
2022 年2 月13 日(オンライン開催)
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N
A1
A2
...
AN
Q
X1
X2
...
XQ
標準出力にQ 行出力せよ.j 行目(1 ≦j ≦Q) には,j 番目の質問の答えを出力せよ.
4
14
9
8
12
6
2
3
5
7
11
13
7
9
1
1
1
3
13
1
4
1
4
2
1
3
5
6
2
3
7
3
8
2
10
11
13
15
17
18
20
1
1
1
1
5
3
1
3
16
536870912
402653184
536870912
536870912
134217728
536870912
671088640
536870912
536870912
536870912
939524096
805306368
536870912
956301312
536870912
536870912
5
2500000000
3355443201
4294967296
5111111111
6190792704
5
1
7
57
1