Mr. Ant Tenna의 TV 타임에 오신 것을 환영합니다! 이번 라운드에서는 $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