35. НОД и запросы (2.0)

У вас есть массивы $A$ и $B$ длины $n + 1$ и $m + 1$ соответственно, состоящие из натуральных чисел. Гарантируется, что $A_0 = B_0 = 1$.

У вас есть также набор натуральных чисел $X_1, X_2, ..., X_k$, каждое из которых больше $1$. Вы должны выбрать некоторый непустой префикс массива $A$ и некоторый непустой префикс массива $B$. Стоимость выбора префикса массива $A$ задана в массиве $CA$, если вы выбираете префикс $i$ массива $A$, то платите $CA_i$. Аналогично заданы стоимости выбора префиксов из массива $B$ в массиве $CB$. При выборе префикса $j$ из массива $B$ вы платите $CB_j$.

Пусть $P_i = \prod_{r = 0}^i A_r$, $Q_j = \prod_{r = 0}^j B_r$, то есть $P$ и $Q$ $-$ произведения элементов на выбранных префиксах в соответствующих массивах. Вам нужно выбрать префиксы $i$ и $j$ так, чтобы $GCD(P_i, Q_j)$ не делился ни на одно из чисел $X_1, X_2, ..., X_k$, а стоимость выбора этих префиксов была минимально возможной из всех способов выбрать два префикса, чтобы выполнялось предыдущее условие. Вам также нужно ответить на $t$ независимых запросов, в каждом из которых задается набор чисел $X$.

В первой строке вам даны три числа $1 \le n \le 2 \cdot 10^4$, $1 \le m \le 2 \cdot 10^4$ и $1 \le q \le 2 \cdot 10^4$ , обозначающие соответственно длину массива $A$, длину массива $B$ и количество запросов. В следующей строке вам заданы элементы массива $A$ $-$ $n + 1$ чисел $1 \le A_i \le 10^9$. В следующей строке вам заданы элементы массива $B$ $-$ $m + 1$ чисел в аналогичном формате. Далее идут две строки, описывающие массивы $CA$ и $CB$ $-$ первая из них содержит $n + 1$ натуральных чисел от $1$ до $10^9$, обозначающие стоимости выбора префикса из массива $A$, вторая содержит $m + 1$ чисел в аналогичном формате, которые обозначают уже стоимости выбора префикса из массива $B$. Затем идут описания $q$ запросов. Каждый запрос содержит одну строку, начинается с числа $1 \le k \le 2 \cdot 10^4$ $-$ количества чисел в запросе, за которым идут $k$ чисел $2 \le X_1, X_2, ..., X_k \le 10^9$ $-$ числа запроса, ни на одно из которых не должен делиться НОД произведения выбранных префиксов. Гарантируется, что сумма $k$ по всем запросам не превосходит $2 \cdot 10^4$.

Выведите $k$ чисел $-$ ответ для каждого запроса.