Задача Гауса

Маловідома історія розповідає, що юний Карл Фрідріх Гаусс був неспокійним на уроках, тому його вчителька придумала завдання, щоб зайняти його увагу.

Вчителька дала йому набір натуральних чисел $F(1),F(2),...,F(k)$. Вважатимемо, що $F(t)=0$ для $t>k$. Також вона дала йому набір щасливих чисел і ціну кожного з них. Якщо $x$ — щасливе число, то $C(x)$ позначає його ціну.

Спочатку на дошці записано натуральне число $a$. На кожному ході Карл повинен виконати одну з наступних дій:

• Якщо на дошці написано число $n$, Карл може замінити його на один з його дільників $m$, менший за $n$. Якщо він вибере число $m$, ціна ходу буде $F(d(n/m))$, де $d(n/m)$ — кількість дільників натурального числа $n/m$ (включаючи $n/m$).

• Якщо $n$ — щасливе число, Карл може залишити його на дошці, і ціна ходу буде $C(n)$.

Карл повинен зробити рівно $l$ ходів, і після цього на дошці повинно залишитися число $b$. Позначимо через $G(a,b,l)$ мінімальну ціну, за яку Карл може цього досягти.

Якщо неможливо виконати $l$ таких ходів, то вважаємо $G(a,b,l)=-1$.

Вчителька задала Карлу $q$ запитів. У кожному запиті Карл отримує числа $a$ і $b$ і повинен обчислити значення $G(a,b,l_1)+G(a,b,l_2)+...+G(a,b,l_m)$, де $l_1,l_2,...,l_m$ однакові для всіх запитів.

Вхідні дані

Перший рядок містить натуральне число $k(1\le k\le 10^4)$.

Другий рядок містить $k$ натуральних чисел $F(1),F(2),...,F(k)$, кожне з яких не перевищує $10^3$.

Наступний рядок містить натуральне число $m(1\le m\le 10^3)$.

Наступний рядок містить $m$ натуральних чисел $l_1,l_2,...,l_m$, кожне з яких не перевищує $10^4$.

Наступний рядок містить натуральне число $t(1\le t\le 50)$ — загальна кількість щасливих чисел.

Кожен з наступних $t$ рядків містить числа $x$ і $C(x)$, де $x$ — щасливе число, а $C(x)$ — його ціна $(1\le x\le 10^6,1\le C(x)\le 10^3)$.

Кожне щасливе число з'являється не більше одного разу.

Наступний рядок містить натуральне число $q(1\le q\le 50000)$.

Кожен з наступних $q$ рядків містить два натуральних числа $a$ і $b(1\le a,b\le 10^6)$.

Вихідні дані

Виведіть $q$ рядків. У $i$-му рядку виведіть відповідь на $i$-й запит, заданий у задачі.

Приклади

$l_1=1$, тому Карл може зробити рівно один хід — замінити число $4$ на число $2$, так що $G(4,2,1)=F(d(2))=1$.

$l_2=2$, тому у Карла є два варіанти:

• Він може замінити число $4$ на число $2$, а потім залишити число $2$ (оскільки це щасливе число), тому він платить ціну $F(d(4/2))+C(2)=1+5=6$.

• Він може залишити число $4$ на першому ході і замінити його на другому ході на число $2$, тому ціна дорівнює $C(4)+F(d(4/2))=10+1=11$.

Перший варіант коштує дешевше, тому $G(4,2,2)=6$.

Відповідь на запит дорівнює $G(4,2,1)+G(4,2,2)=7$.