Task Gauss#11517

Task Gauss

1 second

256 megabytes

Very hard

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)$ F(1), F(2), ..., F(k). We consider $F (t) = 0$ F(t) = 0, for $t > k$ 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, 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))$ 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)$ 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$ 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})$ G(a, b, l_1) + G(a, b, l_2) + ... + G(a, b, l_m), where $l_{1}, l_{2}, ..., l_{m}$ l_1, l_2, ..., l_m are the same for all queries.

Input

The first line contains the positive integer $k (1 \leq k \leq 1 0^{4})$ k\:(1 \le k \le 10^4).

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

The following line contains the positive integer $m (1 \leq m \leq 1 0^{3})$ m\:(1 \le m \le 10^3).

The following line contains $m$ positive integers $l_{1}, l_{2}, ..., l_{m}$ l_1, l_2, ..., l_m that are less than or equal to $1 0^{4}$ 10^4.

The following line contains the positive integer $t (1 \leq t \leq 50)$ 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 its price $(1 \leq x \leq 1 0^{6}, 1 \leq C (x) \leq 1 0^{3})$ (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 \leq q \leq 50000)$ q\:(1 \le q \le 50000).

Each of the following $q$ lines contains two positive integers $a$ and $b (1 \leq a, b \leq 1 0^{6})$ 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$ 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$ G(4, 2, 1) = F(d(2)) = 1.

$l_{2} = 2$ 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$ 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$ C(4) + F(d(4/2)) = 10 + 1 = 11.

The first option costs less, so $G (4, 2, 2) = 6$ G(4, 2, 2) = 6.

The answer to the query is $G (4, 2, 1) + G (4, 2, 2) = 7$ G(4, 2, 1) + G(4, 2, 2) = 7.

Example 1