歡迎嚟到 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