欢迎来到 猪咪 的电视节目时间！在本轮游戏中，您将获得 $n$ 个水桶，其中第 $i$ 个水桶的最大 容量为 $v_i$。游戏开始时，所有水桶都会被注满水，您的任务就是在接下来的 $t$ 秒内尽可能地保持水量。 但这里有个问题：这些水桶是坏的！第 $i$ 个水桶的漏水速度是 $l_i$，也就是说，游戏开始后的每秒钟，第 $i$ 个水桶会漏掉 $l_i$ 体积的水。 在游戏开始前，您可以将任意数量的水桶合并成一个。合并后的水桶容量等于被合并水桶里的最大容 量，漏水速度等于被合并水桶的最小速度。您可以进行任意多次合并操作，但只能在注水之前合并水 桶。

恺哥 提出了 $q$ 个问题，其中第 $i$ 个问题的时间限制是 $t_i$。对于每个 $1 ≤ i ≤ q$，求 $t_i$ 秒后最多共能保 留多少体积的水。

请注意：每个问题是独立的。

输入描述

有多组测试数据。

第一行输入一个整数 $T(1 ≤ T ≤ 5 × 10^4)$ 表示测试数据组数，对于每组测试数据： 第一行输入一个整数 $n(1 ≤ n ≤ 2 × 10^5)$，表示水桶的数量。

第二行输入 $n$ 个整数 $v_1, v_2, \dots , v_n(1 ≤ v_i ≤ 4 × 10^{13})$，其中 $v_i$ 表示第 i 个水桶的容量。

第三行输入 $n$ 个整数 $l_1, l_2, \dots , l_n(0 ≤ li ≤ 10^9)$，其中 $l_i$ 表示第 $i$ 个水桶的漏水速度。

第四行输入一个整数 $q(1 ≤ q ≤ 2 × 10^5)$，表示问题的数量。

第五行输入 $q$ 个整数 $t_1, t_2, \dots , t_q(0 ≤ t_i ≤ 10^9)$，其中 $t_i$ 表示第 $i$ 个问题的时间限制。

保证所有数据 $n$ 之和与 $q$ 之和均不超过 $2 × 10^5$。

输出描述

每组数据输出一行 $q$ 个由单个空格分隔的整数，其中第 $i$ 个整数表示 $t_i$ 秒后最多共能保留多少体积的水。

样例

样例输入1

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

样例输出1

4 14 8
43 67 38 77 48