歡迎來到 Mr. Ant Tenna 的電視時間!在這一輪遊戲中,你會獲得 $n$ 個水桶,其中第 $i$ 個水桶的最大容量為 $v_i$ 單位的水。在遊戲開始時,所有水桶都會被裝滿水,而你的任務是在接下來的 $t$ 秒內盡可能保留最多的水。但這裡有個轉折:這些水桶都是破的!第 $i$ 個水桶的漏水速度為 $l_i$,這意味著在遊戲開始後的每一秒,第 $i$ 個水桶都會漏掉 $l_i$ 單位的水。
在遊戲開始之前,你可以將任意數量的水桶合併為一個。合併後的水桶容量等於所合併水桶中的最大容量,而漏水速度則等於所合併水桶中的最小漏水速度。你可以進行任意多次合併,但所有合併都必須在裝水之前完成。
Tenna 提出了 $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