Việc đặt các camera đo tốc độ của người tham gia giao thông đã hạn chế một phần lỗi vượt quá tốc độ cho phép. Tuy vậy, một số người đã đối phó bằng cách giảm tốc độ nơi có camera và sau đó lại phóng nhanh. Để 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 vào tuyến và thời điểm khi xe rời tuyến, dựa và thời gian đi trên toàn tuyến để xác định mức phạt. Hôm nay, team ICPC của thầy Luna và Tina vừa rời quán nhậu sau buổi tiệc liên hoan 2023 và đi vào đoạn đường có hệ thống bắn tốc độ phức tạp như sau:

Tuyến đường có ~n~ đoạn, đoạn thứ ~i~ có độ dài ~l_i~ và tốc độ tối đa cho phép là ~v_i~, với ~i = 1,2, ..., n~. Gọi ~e~ là độ lớn tối đa vượt tốc độ cho phép trên tuyến, tức là giá trị lớn nhất của hiệu tốc độ đi và tốc độ cho phép ở mỗi đoạn. Nếu ~e > 0~, lái xe sẽ bị phạt theo các mức như sau:

• ~0 < e ≤ a_1~ – mức phạt là ~f_1~ đồng,
• ~a_1 < e ≤ a_2~ – mức phạt là ~f_2~ đồng,
• ~a_2 < e ≤ a_3~ – mức phạt là ~f_3~ đồng,
• . . . cứ thế,
• ~a_{m-1} < e~ – mức phạt là ~f_m~ đồng. Hiện tại đang có số liệu chưa xử lý của ~q~ xe của team ICPC, xe thứ ~i~ vào tuyến ở thời điểm ~s_i~ và ra khỏi tuyến ở thời điểm ~t_i~ với ~i = 1,2,...,q.~ Với mỗi xe hãy xác định mức phạt tối đa chắc chắn đúng về lỗi tốc độ.

Input

• Dòng đầu tiên chứa số nguyên ~n~ với ~1 ≤ n ≤ 10~,
• Dòng thứ 2 chứa ~n~ số nguyên ~v_1, v_2, . . ., v_n~ với ~1 ≤ vi ≤ 10^9, \, 1 \le i \le n~,
• Dòng thứ 3 chứa ~n~ số nguyên ~l_1, l_2, . . ., l_n~ với ~1 ≤ li ≤ 10^9, \, 1 \le i \le n~,
• Dòng thứ 4 chứa số nguyên ~m~ với ~1 ≤ m ≤ 10^5~,
• Dòng thứ 5 chứa ~m-1~ số nguyên tăng dần ~a_1, a_2, . . ., a_{m-1}~ với ~1 ≤ a_i ≤ 10^9, \, 1 \le i \le m-1~, nếu ~m = 1~ thì dòng này rỗng,
• Dòng thứ 6 chứa ~m~ số nguyên tăng dần ~f_1, f_2, . . ., f_n~ với ~1 ≤ f_i ≤ 10^9~ với ~1 \le i \le m~,
• Dòng thứ 7 chứa số nguyên ~q~ với ~1 ≤ q ≤ 10^5~.
• Dòng thứ ~i~ trong ~q~ dòng sau chứa 2 số nguyên ~s_i~ và ~t_i~ với ~1 ≤ s_i < t_i ≤ 10^9~.

Output in ra ~q~ số nguyên, mỗi số trên một dòng cho biết số tiền phạt mỗi xe phải nộp. Dữ liệu đảm bảo, nếu ~s_i~ và ~t_i~ thay đổi không quá ~10^{-5}~ thì số tiền nộp phạt không thay đổi.

Sample input

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

0
800
600

Các subtasks:

• 40% test tương ứng với ~n ≤ 10, m ≤ 10^2 , q ≤ 10^2~
• 30% test tương ứng với ~n ≤ 10, m ≤ 10^2 , q ≤ 10^5~
• 30% test tương ứng với ~n ≤ 10, m ≤ 10^5 , q ≤ 10^5~