Task Gauss

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),...,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$ is 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(n/m))$, where $d(n/m)$ is the number of divisors of the positive integer $n/m$ (including $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 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 of $G(a,b,l_1)+G(a,b,l_2)+...+G(a,b,l_m)$, where $l_1,l_2,...,l_m$ are the same for all queries.

Input

The first line contains the positive integer $k(1\le k\le 10^4)$.

The second line contains $k$ positive integers $F(1),F(2),...,F(k)$ that are less than or equal to $10^3$.

The following line contains the positive integer $m(1\le m\le 10^3)$.

The following line contains $m$ positive integers $l_1,l_2,...,l_m$ that are less than or equal to $10^4$.

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

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 10^6,1\le C(x)\le 10^3)$.

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 two positive integers $a$ and $b(1\le a,b\le 10^6)$.

Output

You must print $q$ lines. The $i$-th line contains the answer to the $i$-th query defined in the task.

Examples

$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(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(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$.