The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Final RoundFebruary 13, 2022 (Online)

1

Intercastellar

In 30XX, due to the constant eﬀorts of scientists and engineers, interaction among diﬀerent planets becomesvery active. Bitaro is a beaver who is working as an ambassador of an exchange program. His task is tointroduce foods from the Earth to the habitants in diﬀerent planets. He will leave for the JOI Planet at 1:00 inthe afternoon.
Now, Bitaro is planning to introduce castella to the habitants in the JOI Planet. The castella was already cut
into several pieces. Castella is a baked sponge cake made of flour, egg, sugar, and starch syrup.
The shape of the castella is a horizontally long rectangular box. It was cut into N pieces. The length of thei-th piece (1 ≤ i ≤ N) from the left is an integer Ai .
A couple of minutes ago, it turned out that the habitants in the JOI Planet do not like even integers. To copewith this problem, you will perform the following sequential operations until pieces of even length disappear.
1. Among the pieces of even length, you choose the rightmost one.
2. You cut the chosen piece into two pieces of equal length. Namely, if the length of the chosen piece is k,k
you cut it into two pieces of length . You do not move the position of the pieces.
2To confirm whether the operations are performed correctly, Bitaro will ask you Q questions. The j-th question(1 ≤ j ≤ Q) is as follows.
• After all the operations are performed, what is the length of the X j -th piece from the left?
Given information of the castella and the questions, write a program which answer the questions.

Task 1- 1 / 5

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Final Round
February 13, 2022 (Online)

Input
Read the following data from the standard input. Given values are all integers.
NA1A2..
.
ANQ
X1
X2..
.
XQ

OutputWrite Q lines to the standard output. The j-th line (1 ≤ j ≤ Q) should contain the answer to the j-th question.

Constraints• 1 ≤ N ≤ 200 000.
• 1 ≤ Ai ≤ 1 000 000 000 (1 ≤ i ≤ N).
• 1 ≤ Q ≤ 200 000.
• 1 ≤ X j ≤ 1 000 000 000 000 000 (= 1015 ) (1 ≤ j ≤ Q).
• X j ≤ X j+1 (1 ≤ j ≤ Q − 1).
• After all the operations are performed, the castella is cut into at least XQ pieces.

Subtasks
1. (25 points) Ai ≤ 8 (1 ≤ i ≤ N).
2. (35 points) N ≤ 1 000, Q ≤ 1 000.
3. (40 points) No additional constraints.

Task 1- 2 / 5

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Final Round
February 13, 2022 (Online)

Sample Input and Output
Sample Input 1Sample Output 14714991811216323571113
In the beginning, the lengths of the pieces of the castella are 14, 9, 8, 12 from the left.
After all the operations are performed, the castella is cut into 15 pieces. The lengths of the pieces are
7, 7, 9, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3 from the left.
This sample input satisfies the constraints of Subtasks 2, 3.

Task 1- 3 / 5

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Final Round
February 13, 2022 (Online)

Sample Input 2Sample Output 2

131114111452

3113356237382101113
15171820This sample input satisfies the constraints of all the subtasks.

Task 1- 4 / 5

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Final Round
February 13, 2022 (Online)

Sample Input 3

Sample Output 3

165536870912

1402653184

7536870912

57

536870912

1134217728
536870912
671088640
536870912
536870912
536870912
939524096
805306368
536870912
956301312
536870912
536870912
52500000000
3355443201
4294967296
5111111111
6190792704
This sample input satisfies the constraints of Subtasks 2, 3.

Task 1- 5 / 5