Background

"Not bad malice."
The woman chuckled.
"But if you show malice toward me, you will die."

You do not know what actions will be considered as showing malice, so you decide to solve a problem to distract yourself.

Problem Description

You are given a sequence $a$ of length $n$ and $q$ queries. The $i$-th query gives $k_i$. For each query, you need to perform the following operations:

1. Compute the average $\mathit{avg}$ of the remaining numbers.
2. Delete the numbers among the remaining ones that satisfy $< \mathit{avg} - k_i$.
3. Repeat the above two steps until no numbers will be deleted.
4. Output how many numbers will remain in the end.

Note: Queries are independent. That is, the numbers are not actually deleted.

Input Format

This problem has multiple testcases.

The first line contains an integer $T$, denoting the number of testcases.
For each testcase, the first line contains two integers $n, q$, denoting the number of elements and the number of queries.
The next line contains $n$ integers, where the $i$-th integer is $a_i$.
The next line contains $q$ integers, where the $i$-th integer is $k_i$.

Output Format

Output a total of $T$ lines. For each line, output $q$ integers, where the $i$-th integer denotes how many numbers will remain after processing the $i$-th query.

5
9 9
19 99 63 39 72 46 97 38 68 
0 6 4 0 7 1 0 3 6 
6 8
88 62 48 50 8 47 
0 6 1 5 2 2 6 1 
6 5
33 3 54 17 26 64 
87 89 92 70 59 
18 19
71 52 77 38 12 34 82 14 57 39 91 7 56 86 35 68 38 14 
9 9 1 5 1 3 4 5 6 1 6 0 3 0 2 1 3 5 8 
10 15
4 77 78 76 5 19 98 94 77 81 
17 43 4 86 2 91 85 4 81 74 44 16 21 69 32 

1 2 2 1 2 2 1 2 2
1 1 1 1 1 1 1 1
6 6 6 6 6
4 4 1 3 1 2 2 3 3 1 3 1 2 1 1 1 2 3 4
7 7 2 10 2 10 10 2 10 10 7 7 7 10 7

1
5 1
20 0 0 0 0
5

5

Hint

Sample Explanation

For the first sample, when $k = 0$, obviously only $99$ will be left.
When $k = 6$, the deletion steps are as follows:

• The average is $60\dfrac{1}{9}$, and $99, 63, 72, 97, 68$ are kept.
• The average is $79.8$, and $99, 97$ are kept.
• The average is $98$, stop deleting.

Constraints

For $100\%$ of the data, it holds that $1 \le n, q \le 10^5$, $1 \le T \le 10$, $0 \le a_i, k_i \le 10^9$.

"Not bad malice."
The woman chuckled.
"And you are quite lucky. If it were in the past, you would have died long ago."

Translated by ChatGPT 5