J. Hello Hello Moon vs Batata
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Moon is playing a game against Batata. Moon has $$$N$$$ items. The $$$i$$$-th item has a power of $$$A_i$$$ and grants $$$C_i$$$ points if it successfully breaks Batata's $$$i$$$-th shield, which has a defense of $$$B_i$$$. Specifically, Moon earns $$$C_i$$$ points if his item's power $$$A_i \ge B_i$$$, and $$$0$$$ points otherwise.

Moon has a special ability: before the game starts, he can choose at most one of his items and change its power to exactly $$$X$$$. Batata will give Moon $$$Q$$$ independent queries.

For each query, Batata provides a modification value $$$X$$$. For each $$$X$$$, determine the maximum total points Moon can earn if he uses his special ability optimally.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — denoting the number of test cases.

For each test case:

The first line contains two integers $$$N, Q$$$ ($$$1 \le N, Q \le 2 \cdot 10^5$$$) — denoting the number of items and queries, respectively.

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \le A_i \le 10^9$$$).

The third line contains $$$N$$$ integers $$$B_1, B_2, \ldots, B_N$$$ ($$$1 \le B_i \le 10^9$$$).

The fourth line contains $$$N$$$ integers $$$C_1, C_2, \ldots, C_N$$$ ($$$1 \le C_i \le 10^9$$$).

The next $$$Q$$$ lines each contain one integer $$$X$$$ ($$$1 \le X \le 10^9$$$) — denotes the given modification value for a query.

It is guaranteed that the sum of $$$N$$$ and the sum of $$$Q$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$Q$$$ lines. Each line should contain one integer, representing the maximum total points Moon can earn for the given modification value $$$X$$$.

Example
Input
1
5 4
1 2 4 5 6
3 1 5 8 7
1 5 5 2 1
3
1
7
8
Output
6
5
10
10