Tàu thăm dò của Alice đang thực hiện một nhiệm vụ thu thập mẫu vật. Mẫu vật thứ ~i~ (~1 \le i \le n~) có khối lượng ~m_i~. Sau khi thu thập xong mẫu vật thứ ~i~, tàu thăm dò có thể thực hiện một trong hai hành động sau:

1) Quay về trung tâm cất để bảo quản các mẫu vật đã thu thập; 2) Tiếp tục di chuyển đến vị trí mẫu vật tiếp theo nếu còn, mẫu vật thứ ~i+1~. Hành động này chỉ thực hiện được nếu tổng khối lượng các mẫu vật mà tàu thăm dò đang mang không vượt quá ~W~.

Cho biết ~d_i~ (~1 \le i < n~) là thời gian để tàu thăm dò di chuyển từ vị trí mẫu vật thứ ~i~ đến vị trí mẫu vật thứ ~i+1~. Còn ~g_i~ (~1 \le i \le n~) là thời gian để tàu thăm dò di chuyển từ vị trí trung tâm đến vị trí mẫu vật thứ ~i~ cũng như là thời gian để tàu thăm dò di chuyển từ mẫu vật thứ ~i~ về trung tâm. Alice muốn điều khiển tàu thăm dò, xuất phát từ trung tâm đi thu thập mẫu vật và cuối cùng kết thúc tại trung tâm với tổng thời gian nhỏ nhất. Giả thiết rằng, khi tàu thăm dò đã tới vị trí mẫu vật thì thời gian thu thập mẫu vật là không đáng kể.

Yêu cầu: Có ~Q~ câu hỏi, mỗi câu hỏi tương ứng với một giá trị ~W~, hãy lập trình tính thời gian nhỏ nhất để thu thập ~n~ mẫu vật theo yêu cầu.

Input

• Dòng đầu tiên ghi số nguyên dương ~n~ (~n \le 10^5~);
• Dòng tiếp theo chứa ~n~ số nguyên dương ~m_1, m_2, \dots, m_n~ (~m_i \le 10^9~);
• Dòng tiếp theo chứa ~n-1~ số nguyên dương ~d_1, d_2, \dots, d_{n-1}~ (~d_i \le 10^9~);
• Dòng tiếp theo chứa ~n~ số nguyên dương ~g_1, g_2, \dots, g_n~ (~g_i \le 10^9~);
• Tiếp theo là số nguyên ~Q~ (~Q \le 100~);
• ~Q~ dòng cuối, mỗi dòng gồm một số nguyên ~W~ (~W \le 10^9~) mô tả một câu hỏi.

Output

• Kết quả gồm ~Q~ dòng, mỗi dòng một số nguyên là câu trả lời tương ứng với câu hỏi trong dữ liệu vào.