Solve this please

There are N boxes. The i-th box a[i] packets of Maggi. So, by picking up the i-th box, you grab a[i] packets of Maggi.

There are Q queries regarding these boxes. For the j-th query you have to answer what is the minimum number of boxes you need to pick up to own at least x[j] packs of Maggi, or print -1 if it’s not possible to obtain such a quantity.

In other words, you should print the minimum possible K such that after picking K boxes, you have at least x[j] packets of Maggi. Note that one box can be chosen once only, and queries are independent of each other (you can use the same box for different queries).

Input

The first line of input contains a single integer T (1 ≤ T ≤ 1000) — the number of test cases. The description of test cases follows.

The first line contains 2 integers N and Q (1 ≤ N , Q ≤ 10^5) — the number of boxes and the number of queries you have to print an answer for respectively.

The second line contains N integers a[1], … , a[n] (1 ≤ a[i] ≤ 10^4) — the number of packs of Maggi in each box.

Then Q lines follow.

Each of the next Q lines contains a single integer x[j] (1≤ x[j] ≤ 10^9) – the number of Maggi packets you want to own for each query.

Output

For each test case output Q lines. For the j-th line output the number of boxes you need to pick up to own at least x[j] packs of Maggi, or print -1 if it’s not possible to obtain such a quantity.

key ideas :

sort the boxes in descending order
use prefix sum and alter the list accordingly
for each qi, check if the jth box is enough - if it is, that will be the number of boxes needed