Dato je n segmenata i m tačaka na x-osi. Za svaku od datih m tačaka odrediti broj segmenata kojima ona pripada. Tačka x pripada segmentu [a, b] ako je a ≤ x ≤ b.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza.) U prvom redu standradnog ulaza nalaze se dva prirodna broja n ≤ 10⁵ i m ≤ 10⁵ - broj segmenata i broj tačaka, redom. U sledećem redu se nalaze m brojeva razdvojenih razmakom - koordinate tačaka. U sledećih n redova se nalaze po dva broja razdvojena razmakom - leva i desna koordinata odgovarajućeg segmenta (leva koordinata je strogo manja od desne). Sve koordinate su prirodni brojevi ne veći od 10⁹.

Izlaz.

(Izlazne podatke ispisati na standardan izlaz.) Na standardni izlaz za svaku tačku ispisati broj segmenata kojima ona pripada, svaki broj u posebnom redu i u redosledu kojim su tačke date na ulazu.

Primer 1.

3 4
5 1 8 9
6 7
4 9
2 5 

2
0
1
1

const
  MaxN = 100010;
  MaxM = 100010;

type
  Point = Record
    x : longint;
    t : longint;
    num : longint;
  end;

var
  a : array[0..2*MaxN + MaxM] of Point;
  sol : array[0..MaxM] of longint;
  n, m, i, sum : longint;
  x, y : Point;


procedure QS(l, r : longint);
var
  i, j: longint;
begin
  i := l; j := r; x := a[(l + r) DIV 2];
  repeat
    while ((a[i].x < x.x) or ((a[i].x = x.x) and (a[i].t > x.t))) do i := i + 1;
    while ((x.x < a[j].x) or ((x.x = a[j].x) and (x.t > a[j].t))) do j := j - 1;
    if (i <= j) then begin
      y := a[i]; a[i] := a[j]; a[j] := y;
      i := i + 1; j := j - 1;
    end;
  until (i > j);
  if (l < j) then QS(l, j);
  if (i < r) then QS(i, r);
end;

begin

   readln(n, m);
   for i := 0 to m - 1 do begin
     read(a[i].x);
     a[i].t := 0;
     a[i].num := i;
   end;
   for i := 0 to n - 1 do begin
     readln(a[m + 2*i].x, a[m + 2*i + 1].x);
     a[m + 2*i].t := 1;
     a[m + 2*i + 1].t := -1;
   end;

   QS(0, m + 2 * n - 1);
   sum := 0;
   for i := 0 to m + 2 * n - 1 do begin
     if (a[i].t = 0) then
       sol[ a[i].num ] := sum
     else
       sum := sum + a[i].t;
   end;

   for i := 0 to m - 1 do
     writeln(sol[i]);

end.

#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MaxN = 100010;
const int MaxM = 100010;


int n, m, sum;

struct Point {
  int x;      // type =  1 => levi kraj segmenta
  int type;    // type =  0 => jedna od m tacaka
  int num;    // type = -1 => desni kraj segmenta
};

Point a[2 * MaxN + MaxM];
int sol[MaxM];

bool cmp(Point A, Point B) {
  return ((A.x < B.x) || (A.x == B.x && A.type > B.type));
}

int main() {

  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d", &a[i].x);
    a[i].type = 0;
    a[i].num = i;
  }
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &a[m + 2 * i].x, &a[m + 2 * i + 1].x);
    a[m + 2 * i].type = 1;  
    a[m + 2 * i + 1].type = -1; 
  }

  sort(a, a + m + 2 * n, cmp);

  sum = 0;
  for (int i = 0; i < m + 2 * n; i++) {
    if (a[i].type == 0) 
      sol[ a[i].num ] = sum;
    else 
      sum += a[i].type;
  }

  for (int i = 0; i < m; i++)
    printf("%d\n", sol[i]);

  return 0;
}