Малоизвестная история о том, что юный Карл Фридрих Гаусс был беспокойным на уроках, поэтому его учитель придумал задание, чтобы не давать ему скучать.
Учитель дал ему набор натуральных чисел F(1),F(2),...,F(k). Будем считать F(t)=0 при t>k. Кроме того, она дала ему набор счастливых чисел и цену каждого счастливого числа. Если x — счастливое число, то C(x) обозначает его цену.
Изначально на доске записано натуральное число a. На каждом ходу Карл должен сделать одно из следующих действий:
Если в данный момент на доске написано число n, то Карл может вместо 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,l1)+G(a,b,l2)+...+G(a,b,lm), где l1,l2,...,lm одинаковы для всех запросов.
Первая строка содержит натуральное число k(1≤k≤104).
Вторая строка содержит k натуральных чисел F(1),F(2),...,F(k), меньших или равных 103.
Следующая строка содержит натуральное число m(1≤m≤103).
Следующая строка содержит m натуральных чисел l1,l2,...,lm, меньше или равных 104.
Следующая строка содержит натуральное число t(1≤t≤50) — общее количество счастливых номеров.
Каждая из следующих t строк содержит числа x и C(x), обозначающие, что x — счастливое число, а C(x) — его цена (1≤x≤106,1≤C(x)≤103).
Каждое счастливое число появляется не более одного раза.
Следующая строка содержит натуральное число q(1≤q≤50000).
Каждая из следующих строк q содержит два натуральных числа a и b(1≤a,b≤106).
Выведите q строк. В i-й строке выведите ответ на i-й запрос, заданный в задаче.
l1=1, поэтому Карл может сделать ровно один ход — заменить число 4 на число 2, так что G(4,2,1)=F(d(2))=1.
L2=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.