LearnToCP
Sign in
Navigation
HomeRoadmapProblemsAbout Us
Theory
Basics
Your First ProgramData types and IOC++ syntaxModuloFunctionsVectorsMatricesTime Complexity
Sorting
SortingCounting sortRadix Sort
Optimization Techniques
Two PointersSum of numbers 1 to nPrefix sumBinary SearchGreedyBinary Search Functions
Binary Numbers
Binary NumbersNumbers in codeBitwise Operations
Math
Binary ExponentiationPrime NumbersPrime FactorizationGCD and LCMSieve of Eratosthenes
Data Structures
StringsStackQueue
Dynamic Programming
About DPDP problems

Above the Threshold

EasyProblem #30
Time LimitMemoryInputOutput
1 s64 MBstdinstdout

Mind the direction in which the scores are sorted.

The national committee is choosing the qualification threshold for the programming olympiad. Maja, the administrator of the scoreboard, keeps being asked the same kind of question: "if the threshold were p points, how many competitors would qualify?" A competitor qualifies when their score is at least p. Help Maja answer all the questions.

Input

First line of input will be a single integer t - the number of testcases. Each testcase consists of three lines:

  • the first contains two integers n and m - the number of competitors and the number of questions.
  • The second line contains n integers - the scores, sorted from the largest to the smallest.
  • The third line contains m integers - the thresholds to answer for.

Output

For every threshold print a single line with the number of competitors whose score is at least that threshold.

Example

Input
1
5 4
89 73 73 56 23
95 50 70 0
Output
0
4
3
5

Nobody has 95 or more points, four competitors have at least 50, three have at least 70, and everyone has at least 0.

Constraints

1≤t≤1000
1≤n,m≤2⋅105
0≤ai​,p≤109
Both the sum of n and the sum of m over all testcases are at most 2⋅105.


This problem was adapted, with permission, from Broj takmičara iznad praga, authored by Društvo matematičara Srbije and Fondacija Petlja.

Submit your solution

Sign in to submit your solution and track your progress.

Sign in to submit