Малоизвестная история о том, что юный Карл Фридрих Гаусс был беспокойным на уроках, поэтому его учитель придумал задание, чтобы не давать ему скучать. Учитель дал ему набор натуральных чисел $F(1), F(2), ..., F(k)$. Будем считать $F(t) = 0$ при $t > k$. Кроме того, она дала ему набор счастливых чисел и цену каждого счастливого числа. Если $x$ --- счастливое число, то $C(x)$ обозначает его цену. Изначально на доске записано натуральное число $a$. На каждом ходу Карл должен сделать одно из следующих действий: \begin{itemize} \item Если в данный момент на доске написано число $n$, то Карл может вместо $n$ написать один из его делителей $m$, меньший $n$. Если он напишет число $m$, цена хода составит $F(d(n/m))$, где $d(n/m)$ --- количество делителей натурального числа $n/m$. (включая $n/m$). \item Если $n$ --- счастливое число, то Карл может оставить это число на доске, и цена хода составит $C(n)$. \end{itemize} Карл должен сделать ровно $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$ одинаковы для всех запросов. \InputFile Первая строка содержит натуральное число $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)$. \OutputFile Выведите $q$ строк. В $i$-й строке выведите ответ на $i$-й запрос, заданный в задаче. \Examples $l_1 = 1$, поэтому Карл может сделать ровно один ход --- заменить число $4$ на число $2$, так что $G(4, 2, 1) = F(d(2)) = 1$. $L_2 = 2$, так что у Карла есть два варианта: \begin{itemize} \item Он может заменить число $4$ на число $2$, а затем оставить число $2$ (потому что это счастливое число), поэтому он платит цену $F(d(4/2)) + C(2) = 1 + 5 = 6$. \item Он может оставить число $4$ на первом ходу и заменить его на втором ходу на число $2$, поэтому цена равна $C(4) + F(d(4/2)) = 10 + 1 = 11$. \end{itemize} Первый вариант стоит дешевле, поэтому $G(4, 2, 2) = 6$. Ответ на запрос равен $G(4, 2, 1) + G(4, 2, 2) = 7$.