Một sự thật ít được biết đến là Carl Friedrich Gauss từng là một cậu bé hiếu động. Vì thế thầy giáo của cậu nghĩ ra một bài toán để cậu có thể ngồi yên một chỗ giải bài.

Thầy giáo cho cậu một dãy các số nguyên ~F(1), F(2), ..., F(K)~. Chúng ta coi ~F(t)=0~ với mọi ~t>K~. Ngoài ra, thầy còn cho cậu một tập các số may mắn và giá của chúng. Nếu ~X~ là một số may mắn, thì ~C(X)~ là giá của nó.

Ban đầu, có một số nguyên dương ~A~ được viết trên bảng. Trong mỗi bước, Carl sẽ thực hiện một trong những việc sau:

• Nếu số ~N~ đang ở trên bảng, Carl có thể thay thế nó bằng một số ~M~ nhỏ hơn và là ước của nó. Nếu cậu viết số ~M~, giá của bước đi là ~F(d(N/M))~ với ~d(N/M)~ là số lượng ước của số nguyên ~N/M~ (tính cả ~N/M~).
• Nếu ~N~ là một số may mắn, Carl có thể để lại số đó trên bảng và giá của bước đi là ~C(N)~.

Carl phải thực hiện chính xác ~L~ bước, và sau khi thực hiện hết các bước trên, số ~B~ phải được viết trên bảng. Gọi ~G(A,B,L)~ là giá nhỏ nhất để làm được điều như trên. Nếu không thể chuyển từ số ~A~ sang số ~B~ trong ~L~ bước thì ~G(A,B,L)=-1~.

Thầy giáo đã cho Carl ~Q~ truy vấn. Mỗi truy vấn gồm ~2~ số ~A~ và ~B~ và Carl cần tính ~G(A,B,L_1)+G(A,B,L_2)\:+...+\:G(A,B,L_M)~, với ~L_1,L_2,...,L_M~ là các số không đổi qua các truy vấn.

Input

• Dòng đầu tiên gồm số nguyên dương ~K~ ~(1 \le K \le 10\:000)~.

• Dòng thứ hai gồm ~K~ số nguyên dương ~F(1), F(2),...,F(K)~ ~(1 \le F(i) \le 1000,\: 1 \le i \le K)~.

• Dòng tiếp theo gồm số nguyên dương ~M~ ~(1 \le M \le 1\:000)~.

• Dòng tiếp theo gồm ~M~ số nguyên dương ~L_1,L_2,...,L_M~ ~(1 \le L_i \le 10\:000, \: 1 \le i \le M)~.

• Dòng tiếp theo gồm số nguyên dương ~T~ ~(1 \le T \le 50)~ là số lượng số may mắn.

• ~T~ dòng tiếp theo, mỗi dòng gồm số may mắn ~X~ ~(1 \le X \le 1\:000\:000)~ và giá của nó là ~C(X)~ ~(1 \le C(X) \le 1\:000)~. Mỗi số may mắn chỉ xuất hiện một lần.

• Dòng tiếp theo gồm số nguyên dương ~Q~ ~(1 \le Q \le 50\:000)~.

• ~Q~ dòng tiếp theo mỗi dòng gồm ~2~ số nguyên dương ~A,B~ ~(1 \le A,B \le 1\:000\:000)~.

Output

In ra ~Q~ dòng. Dòng thứ ~i~ chứa đáp án cho truy vấn thứ ~i~.

Sample 1

Input

4
1 1 1 1
2
1 2
2
2 5
4 10
1
4 2

Output

7

Giải thích

~L_1 = 1~ nên Carl chỉ có ~1~ lựa chọn. Thay số ~4~ bằng số ~2~. Do đó ~G(4,2,1)=F(d(2))=1~.

~L_2 = 2~ nên Carl có ~2~ lựa chọn:

• Thay số ~4~ thành số ~2~ và giữ nguyên số ~2~ vì ~2~ là số may mắn, giá của cách đi này là ~F(d(4/2))+C(2) = 1+5 = 6~
• Giữ nguyên số ~4~ trong bước đầu, và thay thành số ~2~ ở bước sau, giá của cách đi là ~C(4)+F(d(4/2)) = 10+1 = 11~.

Lựa chọn đầu tiên tốn ít hơn nên ~G(4,2,2)=6~.

Vậy đáp án cho truy vấn là ~G(4,2,1)+G(4,2,2)=1+6=7~.

Sample 2

Input

3
6 9 4
2
5 7
3
1 1
7 8
6 10
2
6 2
70 68

Output

118
-2

Sample 3

Input

3
8 3 10
2
8 4
3
1 6
5 1
3 7
2
5 1
3 1

Output

16
66