Quals-I-2011-4
n segments and m points on x-axis are given. For each of the m given points determine the number of segments that contain the given point. Point x belongs to segment [a,b] if a <= x <= b.
Input The first line of the standard input contains 2 natural numbers 1 <= n <= 10^5 and 1<= m <= 10^5 - number of segments and number of points, respectively. Next line contains m numbers delimited by space - coordinates of points. Each of the next n lines contains 2 numbers delimited by space - left and right coordinate of the corresponding segment (left coordinate is strictly less then the right coordinate). All coordinates are natural numbers not greater than 10^9.
Output To the standard output for each point write the number of segments that contain it. All numbers should be written in separate lines and in the same order as the points in the input.
Input:
3 4
5 1 8 9
6 7
4 9
2 5 Output:
2
0
1
1
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.