Mô tả vấn đề

Có ~ N ~ ô vuông liên tiếp, được đánh số từ ~ 1 ~ đến ~ N ~ từ trái sang phải. Snuke và Rng đang chơi trò chơi trên bàn cờ bằng cách sử dụng các ô vuông này, được mô tả dưới đây:

1. Đầu tiên, Snuke viết một số nguyên vào mỗi ô vuông.
2. Mỗi người trong hai người chơi sở hữu một mảnh. Snuke đặt quân cờ của mình vào ô vuông ~ 1 ~, và Rng đặt quân cờ vào ô vuông ~ 2 ~.
3. Người chơi có quân cờ ở bên trái đối phương sẽ di chuyển quân cờ của mình. Đích đến phải là một hình vuông ở bên phải của hình vuông nơi quân cờ đang được đặt và không được vào hình vuông nơi quân cờ của đối thủ được đặt.
4. Lặp lại bước 3. Khi các quân cờ không thể di chuyển được nữa, trò chơi kết thúc.
5. Điểm của mỗi người chơi được tính bằng tổng các số nguyên được viết trong các ô vuông mà người chơi đã đặt quân cờ của mình trước khi kết thúc trò chơi.

Snuke đã viết một số nguyên ~ A_i ~ vào hình vuông ~ i (1 ≤ i ≤ N-1) ~, nhưng không viết vào hình vuông thứ ~ N ~. Anh ấy đã quyết định tính toán cho mỗi ~ M ~ số nguyên ~ X_1, X_2, ..., X_M ~, nếu anh ấy viết nó vào ô vuông ~ N ~ và trò chơi được chơi, giá trị Điểm của Snuke - Điểm của Rng sẽ được là bao nhiêu. Ở đây, người ta giả định rằng mỗi người chơi di chuyển quân cờ của mình để tối đa hóa giá trị điểm của người chơi - điểm của đối thủ.

Hạn chế

• ~ 3 ≤ N ≤ 200.000 ~
• ~ 0 ≤ A_i ≤ 10 ^ 6 ~
• Tổng của tất cả ~ A_i ~ nhiều nhất là ~ 10 ^ 6 ~.
• ~ 1 ≤ M ≤ 200.000 ~
• ~ 0 ≤ X_i ≤ 10 ^ 9 ~

Đầu vào

Đầu vào được cung cấp theo định dạng sau:

~ N ~

~ A_1 ~ ~ A_2 ~ ~ ... ~ ~ A_ {N-1} ~

~ M ~

~ X_1 ~

~ X_2 ~

~: ~

~ X_M ~

Đầu ra

Đối với mỗi số nguyên ~ M ~ ~ X_1, ..., X_M ~, in ra giá trị "(Điểm của Snuke) - (Điểm của Rng)" nếu nó được viết thành ô vuông ~ N ~, một trên mỗi dòng.

Đầu vào Mẫu 1

5
2 7 1 8
1
2

Đầu ra Mẫu 1

0

Trò chơi diễn ra như sau, trong đó Sđại diện cho quân của Snuke vàR đại diện cho Rng.

Điểm của cả hai người chơi là ~ 10 ~, do đó "(Điểm của Snuke) - (Điểm của Rng)" là ~ 0 ~.

Đầu vào Mẫu 2

9
2 0 1 6 1 1 2 6
5
2016
1
1
2
6

Đầu ra Mẫu 2

2001
6
6
7
7