Snake Eating

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
The Chef has acquired a vicious bunch of snakes, and these snakes are ever hungry and end up eating each other. In particular, each snake i has a length L_{i}, whose initial value is given to you. A snake can eat any other snake which is not longer than itself. That is, snake i can eat snake j (i ≠ j), if L_{i} ≥ L_{j}. And when a snake eats another snake, its length increases by 1. That is, L_{i} increases by 1. A snake can eat multiple other snakes.
The Chef doesn't care about snakes eating each other. All he wants is to have as many snakes as possible, which are at least some particular lengths long. You are given Q values: K_{1}, K_{2}, .., K_{Q}. Treat each of them independently and output the answer for each. That is, for each K_{i}, assume that you start out from the beginning with all the snakes alive and the lengths as the initial values given in the input, and find out the maximum number of snakes you can get whose length is at least K_{i}.
Input
 The first line contains an integer T, which is the number of testcases. The description of each testcase follows.
 The first line of each testcase contains two integers: N and Q, which denote the number of snakes initially, and the number of queries, respectively.
 The second line contains N space separated integers: L_{1}, L_{2}, .., L_{N}, the initial lengths of the snakes.
 The ith of the next Q lines contains a single integer, K_{i}.
Output
 For each testcase, output Q lines, the ith of which should have a single integer: The maximum number of snakes the Chef can get which are of length at least K_{i}.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N, Q ≤ 10^{5}
 1 ≤ L_{i} ≤ 10^{9}
 1 ≤ K_{i} ≤ 10^{9}
Example
Input: 2 5 2 21 9 5 8 10 10 15 5 1 1 2 3 4 5 100 Output: 3 1 0
Explanation
In the first testcase, first query, the second snake (length 9) can eat the fourth snake (length 8), and hence make its length 10. Now, there are four snakes left, and their lengths are {21, 10, 5, 10}. So, we have three snakes with length ≥ 10: Two snakes of length 10 and one snake of length 21. This is the best you can do.
In the second query, no matter what happens, you cannot get more than one snake of length ≥ 15.
In the second testcase, no matter what happens, you cannot get any snake of length ≥ 100. Hence the answer is 0.
Author:  admin3 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/SNAKEEAT 
Tags  admin3, binarysearch, easy, snckql17, sorting, vivek1_007 
Date Added:  18052017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions