It is a little-known story that the young Carl Friedrich Gauss was restless in class, so his teacher came up with a task to keep him preoccupied.

The teacher gave him a series of positive integers ~F(1), F(2), \dots, F(K)~. We consider ~F(t) = 0~ for ~t > K~. Additionally, she has given him a set of lucky numbers and the price of each lucky number. If ~X~ is a lucky number, then ~C(X)~ denotes its price.

Initially, there's a positive integer ~A~ written on the board. In each move, Carl must make one of the following things:

• If number ~N~ is currently written on the board, then Carl can write one of its divisors ~M~, smaller than ~N~, instead of ~N~. If he writes the number ~M~, the price of the move is ~F(d(\frac{N}{M}))~, where ~d(\frac{N}{M})~ is the number of divisors of the positive integer ~\frac{N}{M}~ (including ~\frac{N}{M}~).
• If ~N~ is a lucky number, Carl can leave that number on the board, and the price of the move is ~C(N)~.

Carl must make exactly ~L~ moves, and after he has made all of his moves, the number ~B~ must be written on the board. Let's denote ~G(A, B, L)~ as the minimal price with which Carl can achieve this.

If it is not possible to make ~L~ such moves, we define ~G(A, B, L) = -1~.

The teacher has given Carl ~Q~ queries. In each query, Carl gets numbers ~A~ and ~B~ and must calculate the value ~G(A, B, L_1) + G(A, B, L_2) + \dots + G(A, B, L_M)~, where numbers ~L_1, L_2, \dots, L_M~ are the same for all queries.

Input Specification

The first line of input contains the positive integer ~K~ ~(1 \le K \le 10\,000)~.

The second line contains ~K~ positive integers ~F(1), F(2), \dots, F(K)~ that are less than or equal to ~1\,000~.

The following line contains the positive integer ~M~ ~(1 \le M \le 1\,000)~.

The following line contains ~M~ positive integers ~L_1, L_2, \dots, L_M~ that are less than or equal to ~10\,000~.

The following line contains the positive integer ~T~, the total number of lucky numbers ~(1 \le T \le 50)~.

Each of the following ~T~ lines contains numbers ~X~ and ~C(X)~ that denote that ~X~ is a lucky number, and ~C(X)~ is his price ~(1 \le X \le 1\,000\,000, 1 \le C(X) \le 1\,000)~. Each lucky number appears at most once.

The following line contains the positive integer ~Q~ ~(1 \le Q \le 50\,000)~.

Each of the following ~Q~ lines contains ~2~ positive integers ~A~ and ~B~ ~(1 \le A, B \le 1\,000\,000)~.

Output Specification

You must output ~Q~ lines. The ~i^\text{th}~ line contains the answer to the ~i^\text{th}~ query defined in the task.

Sample Input 1

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

Sample Output 1

7

Explanation for Sample Output 1

~L_1 = 1~, so Carl can make exactly one move - replace number ~4~ with number ~2~, so ~G(4, 2, 1) = F(d(2)) = 1~.

~L_2 = 2~, so Carl has two options:

• He can replace number ~4~ with number ~2~ and then leave number ~2~ (because it's a lucky number), so he pays the price ~F(d(\frac{4}{2})) + C(2) = 1 + 5 = 6~.
• He can leave number ~4~ in the first move, and replace it in the second move with number ~2~, so the price is ~C(4) + F(d(\frac{4}{2})) = 10 + 1 = 11~.

The first option costs less, so ~G(4, 2, 2) = 6~. The answer to the query is ~G(4,2,1) + G(4,2,2) = 7~.

Sample Input 2

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

Sample Output 2

118
-2

Sample Input 3

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

Sample Output 3

16
66