Tèo chuẩn bị về quê ăn tết, nhưng Tèo còn chưa làm xong bài tập thầy giao. Tèo đang có ~n~ bài tập còn đang dở, bài thứ ~i~ anh ấy biết chắc rằng mình sẽ hoàn thành trong ~t_i~ phút và sẽ được ~v_i~ điểm. Các bài được sắp xếp theo độ khó giảm dần, do Tèo có sở thích làm bài khó thì giỏi còn bài dễ thì ngu nên với mỗi cặp ~(i, j)~ sao cho ~i \leq j~ thì ~t_i \leq t_j~ và ~v_i \geq v_j~.

Vì gần đến deadline rồi nên Tèo muốn giải bài tập để được nhiều điểm nhất có thể. Câu hỏi của Tèo như sau: Nếu chỉ còn ~x~ phút thì Tèo sẽ chọn các bài để làm như thế nào sao cho được nhiều điểm nhất.

Input

• Dòng đầu tiên nhập số ~n~ ~(1 \leq n \leq 10^5)~ là số bài Tèo được giao.

• Dòng thứ ~2~ gồm ~n~ số nguyên dương ~t_1,t_2,...,t_n~ ~(1 \leq t_i \leq 10^9)~ với ~t_i~ là thời gian Tèo làm bài tập của bài thứ ~i~.

• Dòng thứ ~3~ gồm ~n~ số nguyên dương ~v_1,v_2,...,v_n~ ~(1 \leq v_i \leq 10^9)~ với ~v_i~ là số điểm của bài thứ ~i~.

• Dòng thứ ~4~ gồm số ~Q~ ~(1 \leq Q \leq 10^5)~ là số lượng câu hỏi mà Tèo đặt ra.

• ~Q~ dòng tiếp theo, dòng thứ ~i~ gồm số nguyên dương ~x_i~ ~(1 \leq x_i \leq 10^{14})~ là lượng thời gian Tèo có cho câu hỏi thứ ~i~.

Output

• Gồm ~Q~ dòng, dòng thứ ~i~ là đáp số cho câu hỏi thứ ~i~.

Sample Input

5
2 2 3 4 5
5 4 3 2 1
2
8
1

Sample Output

12
0

Note

Với test ví dụ trên:

• Khi Tèo còn ~8~ phút, anh có thể làm bài ~3~ bài đầu tiên, khi đó điểm mà Tèo nhận được là ~5 + 4 + 3 = 12~ và mất ~2 + 2 + 3 = 7~ phút. Có thể chứng minh đây là cách làm tối ưu.
• Khi Tèo còn ~1~ phút, anh không thể làm bài nào hết trong ~5~ bài thầy giao, vì thể điểm của anh là ~0~.

Constraint