Ласкаво просимо на шоу «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