Lái xe vượt quá tốc độ cho phép là nguyên nhân của nhiều tai nạn giao thông nghiêm trọng. Để kiểm soát tốc độ chung trên toàn tuyến đường, người ta đặt camera ghi nhận thời điểm xe đi vào và rời khỏi tuyến, sau đó dựa vào tổng thời gian di chuyển để xác định mức phạt.

Xét một tuyến đường gồm ~n~ đoạn. Đoạn thứ ~i~ có độ dài ~l_i~ và tốc độ tối đa cho phép là ~v_i~ ~(1 \le i \le n)~.

Gọi ~e~ là độ vượt quá tốc độ cho phép lớn nhất trên toàn tuyến, tức là giá trị lớn nhất của hiệu giữa tốc độ di chuyển và tốc độ tối đa cho phép trên mỗi đoạn. Nếu ~e>0~, người lái xe bị phạt theo các mức sau:

• Nếu ~0<e\le a_1~ thì mức phạt là ~f_1~ đồng;</p>

• Nếu ~a_1<e\le a_2~ thì mức phạt là ~f_2~ đồng;</p>

• Nếu ~a_2<e\le a_3~ thì mức phạt là ~f_3~ đồng;</p>

• ~\ldots~

• Nếu ~a_{m-2}<e\le a_{m-1}~ thì mức phạt là ~f_{m-1}~ đồng;</p>

• Nếu ~a_{m-1}<e~ thì mức phạt là ~f_m~ đồng.</p>

Nếu ~e\le 0~ thì người lái xe không bị phạt.

Hiện có dữ liệu chưa xử lý của ~q~ xe. Xe thứ ~i~ đi vào tuyến tại thời điểm ~s_i~ và rời khỏi tuyến tại thời điểm ~t_i~.

Yêu cầu: Với mỗi xe, hãy xác định mức phạt lớn nhất có thể khẳng định chắc chắn mà xe đó phải nộp do vượt tốc độ.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10)~;

• Dòng thứ hai chứa ~n~ số nguyên ~v_1,v_2,\ldots,v_n~ ~(1 \le v_i \le 10^9)~;

• Dòng thứ ba chứa ~n~ số nguyên ~l_1,l_2,\ldots,l_n~ ~(1 \le l_i \le 10^9)~;

• Dòng thứ tư chứa số nguyên ~m~ ~(1 \le m \le 10^5)~;

• Dòng thứ năm chứa ~m-1~ số nguyên tăng dần ~a_1,a_2,\ldots,a_{m-1}~ ~(1 \le a_i \le 10^9)~. Nếu ~m=1~ thì dòng này rỗng;

• Dòng thứ sáu chứa ~m~ số nguyên tăng dần ~f_1,f_2,\ldots,f_m~ ~(1 \le f_i \le 10^9)~;

• Dòng thứ bảy chứa số nguyên ~q~ ~(1 \le q \le 10^5)~;

• Mỗi dòng trong ~q~ dòng tiếp theo chứa hai số nguyên ~s_i~ và ~t_i~ ~(1 \le s_i<t_i\le 10^9)~.</p>

Output

Ghi ra ~q~ số nguyên, mỗi số trên một dòng, là số tiền phạt tương ứng với mỗi xe.

Dữ liệu bảo đảm rằng nếu ~s_i~ và ~t_i~ thay đổi không quá ~10^{-5}~ thì số tiền phạt không thay đổi.

Scoring

Sample Input 1

3
10 20 30
400 500 600
6
1 5 10 12 16
100 300 600 800 1000 1500
3
10 100
20 70
45 100

Sample Output 1

0
800
600