LearnToCP
Sign in
Navigation
HomeRoadmapProblemsAbout Us
Theory
Contest Knowledge
Selecting an IDE
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 FunctionsBinary Search by AnswerDivide and Conquer
Binary Numbers
Binary NumbersNumbers in codeBitwise OperationsBitmasks
Math
Binary ExponentiationPrime NumbersPrime FactorizationGCD and LCMSieve of EratosthenesModified Sieve
Data Structures
StringsStackQueueMapsSetsPriority QueueCustom Criteria for FunctionsSegment TreesFenwick TreesSparse TablesUnion Find
Combinatorics
Addition PrincipleMultiplication PrincipleCombinatoric ObjectsInclusion Exclusion Principle
Geometry
Geometry BasicsVectorsCross and Dot ProductLinesPolygonsAnglesPoint in PolygonDistances and Intersection PointsConvex HullCircles
Recursion
PointersRecursionGenerating Combinatoric Objects
Dynamic Programming
About DPTree DPBitmask DPDigit DP
Graph Theory
GraphsDFS and BFSShortest PathsTreesTopological SortingDijkstra's AlgorithmMinimum Spanning TreesShortest Path Algorithms
Advanced Graph Theory
BiconnectivityStrongly Connected ComponentsBipartite GraphGraph FlowAugmenting PathsFlow - Minimum Cut DualityHeavy-Light DecompositionCentroid Decomposition
Advanced Data Structures
2D and 3D Segment TreesLazy PropagationImplicit Segment TreesPersistent Segment TreesLowest Common AncestorTrieBalanced Binary Search TreesMo's Algorithm

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