[Solution] Eating Queries solution codeforces

Eating Queries solution codeforces – Timur has 𝑛n candies. The 𝑖i-th candy has a quantity of sugar equal to 𝑎𝑖ai. So, by eating the 𝑖i-th candy, Timur consumes a quantity of sugar equal to 𝑎𝑖ai.

[Solution] Eating Queries solution codeforces

Timur will ask you 𝑞q queries regarding his candies. For the 𝑗j-th query you have to answer what is the minimum number of candies he needs to eat in order to reach a quantity of sugar greater than or equal to 𝑥𝑗xj 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 eating 𝑘k candies, Timur consumes a quantity of sugar of at least 𝑥𝑗xj or say that no possible 𝑘k exists.

Note that he can’t eat the same candy twice and queries are independent of each other (Timur can use the same candy in different queries).

Input

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

[Solution] Eating Queries solution codeforces

The first line contains 22 integers 𝑛n and 𝑞q (1𝑛,𝑞1.51051≤n,q≤1.5⋅105) — the number of candies Timur has and the number of queries you have to print an answer for respectively.

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1041≤ai≤104) — the quantity of sugar in each of the candies respectively.

Then 𝑞q lines follow.

Each of the next 𝑞q lines contains a single integer 𝑥𝑗xj (1𝑥𝑗21091≤xj≤2⋅109) – the quantity Timur wants to reach for the given query.

It is guaranteed that the sum of 𝑛n and the sum of 𝑞q over all test cases do not exceed 1.51051.5⋅105.

Output

For each test case output 𝑞q lines. For the 𝑗j-th line output the number of candies Timur needs to eat in order to reach a quantity of sugar greater than or equal to 𝑥𝑗xj or print -1 if it’s not possible to obtain such a quantity.

[Solution] Eating Queries solution codeforces

Example
input

Copy
3
8 7
4 3 3 1 1 4 5 9
1
10
50
14
15
22
30
4 1
1 2 3 4
3
1 2
5
4
6
output

Copy
1
2
-1
2
3
4
8
1
1
-1

[Solution] Eating Queries solution codeforces

For the first test case:

For the first query, Timur can eat any candy, and he will reach the desired quantity.

For the second query, Timur can reach a quantity of at least 1010 by eating the 77-th and the 88-th candies, thus consuming a quantity of sugar equal to 1414.

For the third query, there is no possible answer.

For the fourth query, Timur can reach a quantity of at least 1414 by eating the 77-th and the 88-th candies, thus consuming a quantity of sugar equal to 1414.

For the second test case:

For the only query of the second test case, we can choose the third candy from which Timur receives exactly 33 sugar. It’s also possible to obtain the same answer by choosing the fourth candy.

For Solution

Click here

Leave a Comment