Mr. Ant Tenna の TV タイムへようこそ!このラウンドのゲームでは $n$ 個のバケツが与えられ、$i$ 番目のバケツには最大で $v_i$ の体積の水を入れることができます。ゲーム開始時にすべてのバケツは水で満杯にされ、あなたの使命は次の $t$ 秒間でできるだけ多くの水をバケツの中に残すことです。しかし、ここで厄介な点があります。これらのバケツは壊れているのです!$i$ 番目のバケツの漏水速度は $l_i$ であり、ゲーム開始後 1 秒ごとに $i$ 番目のバケツから $l_i$ の体積の水が漏れ出します。
ゲーム開始前に、任意の個数のバケツを 1 つに統合することができます。統合後のバケツの容量は統合したバケツの最大容量に等しくなり、漏水速度は統合したバケツの最小漏水速度に等しくなります。統合は任意の回数行うことができますが、すべて水を入れる前に行わなければなりません。
Tenna は $q$ 個の質問を出します。$i$ 番目の質問には制限時間 $t_i$ があります。各 $1 \le i \le q$ について、$t_i$ 秒後に残っている水の総体積の最大値を求めてください。なお、各質問は独立です。
入力
複数のテストケースが与えられます。入力の 1 行目にはテストケースの個数を表す整数 $T$($1 \le T \le 5 \times 10^4$)が与えられます。各テストケースについて:
1 行目にはバケツの個数を表す整数 $n$($1 \le n \le 2 \times 10^5$)が与えられます。
2 行目には $n$ 個の整数 $v_1, v_2, \cdots, v_n$($1 \le v_i \le 4 \times 10^{13}$)が与えられます。ここで $v_i$ は $i$ 番目のバケツの容量です。
3 行目には $n$ 個の整数 $l_1, l_2, \cdots, l_n$($0 \le l_i \le 10^9$)が与えられます。ここで $l_i$ は $i$ 番目のバケツの漏水速度です。
4 行目には質問の個数を表す整数 $q$($1 \le q \le 2 \times 10^5$)が与えられます。
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$ 個の整数を 1 行に出力してください。ここで $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