Vào năm 30XX, nhờ những bước tiến của khoa học và công nghệ, việc giao lưu giữa các hành tinh đã trở nên phổ biến. Hải ly Bitaro được bổ nhiệm làm đại sứ giới thiệu ẩm thực Trái Đất tới người ngoài hành tinh. Hôm nay, lúc 1 giờ chiều, cậu dự định khởi hành tới hành tinh JOI.

Món ăn được chuẩn bị để giới thiệu lần này là bánh castella đã cắt sẵn. Castella là một loại bánh xốp làm chủ yếu từ bột mì, trứng, đường và siro tinh bột. Bánh có dạng hình hộp chữ nhật dài theo chiều ngang và đã được cắt thành \(N\) miếng bằng các đường cắt dọc. Miếng thứ \(i\) tính từ trái sang phải (\(1 \le i \le N\)) có chiều dài \(A_i\).

Vừa mới đây, người ta phát hiện rằng cư dân hành tinh JOI ghét các số chẵn. Để giải quyết việc này, thao tác sau được lặp lại cho đến khi không còn miếng bánh nào có chiều dài chẵn:

1. Chọn miếng ngoài cùng bên phải trong số các miếng có chiều dài chẵn.
2. Gọi chiều dài miếng đã chọn là \(k\). Cắt dọc miếng này thành hai miếng dài \(\frac{k}{2}\), giữ nguyên vị trí tương đối của chúng và các miếng còn lại.

Bitaro chuẩn bị \(Q\) câu hỏi để kiểm tra xem các thao tác có được thực hiện đúng hay không. Câu hỏi thứ \(j\) (\(1 \le j \le Q\)) là: sau khi tất cả các thao tác kết thúc, miếng thứ \(X_j\) tính từ trái sang phải dài bao nhiêu?

Cho thông tin về các miếng bánh ban đầu và các câu hỏi, hãy trả lời từng câu hỏi.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(A_i\).
• Dòng tiếp theo chứa số nguyên \(Q\).
• \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa \(X_j\).

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(j\) chứa đáp án cho câu hỏi thứ \(j\).

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le A_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).
• \(1 \le Q \le 200\,000\).
• \(1 \le X_j \le 10^{15}\) với mọi \(1 \le j \le Q\).
• \(X_j \le X_{j+1}\) với mọi \(1 \le j < Q\).
• Sau khi tất cả các thao tác kết thúc, có ít nhất \(X_Q\) miếng bánh.

Phân nhóm

• Nhóm 1 (25 điểm): \(A_i \le 8\) với mọi \(1 \le i \le N\).
• Nhóm 2 (35 điểm): \(N \le 1000\), \(Q \le 1000\).
• Nhóm 3 (40 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

Nguồn

JOI 2021/2022, vòng chung kết, ngày 13/02/2022. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Nhật, tiếng Anh. Bản dịch theo giấy phép CC BY-SA 4.0.