Добро пожаловать в шоу «TV Time» мистера Ант Тенны! В этом раунде игры вам даны $n$ вёдер, где $i$-е ведро имеет максимальную вместимость $v_i$ единиц объёма воды. В начале игры все вёдра полностью наполняются водой, и ваша задача — сохранить как можно больше воды в течение следующих $t$ секунд. Но вот в чём подвох: эти вёдра дырявые! У $i$-го ведра скорость протечки равна $l_i$, что означает, что каждую секунду после начала игры из $i$-го ведра вытекает $l_i$ единиц объёма воды.
До начала игры вы можете объединить любое количество вёдер в одно. Получившееся ведро будет иметь вместимость, равную максимальной вместимости среди объединённых вёдер, и скорость протечки, равную минимальной скорости протечки среди объединённых вёдер. Вы можете выполнять объединения произвольное число раз, но все они должны быть выполнены до наполнения вёдер водой.
Тенна задаёт $q$ вопросов, где $i$-й вопрос имеет ограничение по времени $t_i$. Для каждого $1 \le i \le q$ вычислите максимальный суммарный сохранённый объём воды через $t_i$ секунд. Обратите внимание, что все вопросы независимы.
Входные данные
Входные данные состоят из нескольких наборов входных данных. Первая строка содержит целое число $T$ ($1 \le T \le 5 \times 10^4$) — количество наборов входных данных. Для каждого набора входных данных:
Первая строка содержит целое число $n$ ($1 \le n \le 2 \times 10^5$) — количество вёдер.
Вторая строка содержит $n$ целых чисел $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), где $v_i$ — вместимость $i$-го ведра.
Третья строка содержит $n$ целых чисел $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), где $l_i$ — скорость протечки $i$-го ведра.
Четвёртая строка содержит целое число $q$ ($1 \le q \le 2 \times 10^5$) — количество вопросов.
Пятая строка содержит $q$ целых чисел $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), где $t_i$ — ограничение по времени для $i$-го запроса.
Гарантируется, что ни сумма $n$, ни сумма $q$ по всем наборам входных данных не превысит $2 \times 10^5$.
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую $q$ целых чисел, разделённых пробелом, где $i$-е число — максимальный суммарный сохранённый объём воды через $t_i$ секунд.
Примеры
2
4
5 4 7 6
2 1 3 2
3
3 1 2
4
19 47 21 13
5 14 2 3
5
5 2 6 1 4
4 14 8
43 67 38 77 48