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)+\cdots +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 10000)$.

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

The following line contains the positive integer $M$ $(1\le M\le 1000)$.

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

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 1000000,1\le C(X)\le 1000)$. Each lucky number appears at most once.

The following line contains the positive integer $Q$ $(1\le Q\le 50000)$.

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

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