아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Сколько звезд на небе?

시간 제한4초메모리 제한1024 MB

요약
N개의 점이 주어질 때, M개의 축에 나란한 직사각형 각각에 대해 내부나 경계에 포함되는 점의 수를 구한다.
난이도

보통10점 중 6점

유형
정렬, 이분 탐색, 누적 합, 구간
정답자
아직 제출이 없습니다

문제

Британские ученые решили посчитать, сколько звезд на небе. Для этого они построили супермегателескоп, в который, если никто не мешает, можно разглядеть муху на поверхности Альфа Центавры. Чтобы обрабатывать данные, поступающие с этого телескопа, они построили супермегакластер, способный просчитать движение всех звезд Млечного Пути на сорок восемь миллионов лет вперед. Для решения проблемы энергоснабжения этого кластера британские ученые обратились к своим швейцарским друзьям, и те поделились с ними энергией Большого Адронного Коллайдера. И вот процесс начался.

Итак, на небе NN звезд. Так как для упрощения модели небо решили аппроксимировать плоскостью, то у каждой звезды есть координаты X_i,Y_iX\_i, Y\_i. Координаты звезд вычислены с поражающей воображение точностью, поэтому можно считать, что ни у каких двух звезд координаты не совпадают.

Теперь британские ученые хотят собрать статистику. Для этого они сформулировали MM запросов, каждый из которых звучит так: <<Сколько звезд находится внутри или на границе области, заданной следующими неравенствами: X_jmin≤x≤X_jmaxX\_j^{min} \le x \le X\_j^{max}, Y_jmin≤y≤Y_jmaxY\_j^{min} \le y \le Y\_j^{max}?>>

К сожалению, из-за неожиданного извержения вулкана британские ученые не смогли собраться на очередное заседание, чтобы вычислить результаты запросов. Поэтому они просят Вас помочь им.

입력

В первой строке входного файла даны два целых числа NN (1≤N≤1000001 \le N \le 100000) и MM (1≤M≤500001 \le M \le 50000) --- число звезд на небе и число запросов соответственно.

Далее в NN строках заданы координаты звезд --- пары целых чисел (X_i,Y_iX\_i, Y\_i) (∣X_i∣,∣Y_i∣≤109|X\_i|, |Y\_i| \le 10^9). Никакие две звезды не совпадают.

Далее в MM строках заданы запросы --- четверки целых чисел (X_jmin,X_jmax,Y_jmin,Y_jmaxX\_j^{min}, X\_j^{max}, Y\_j^{min}, Y\_j^{max}). Все величины в описании запросов не превосходят 10910^9 по абсолютному значению. Гарантируется, что X_jmin≤X_jmaxX\_j^{min} \le X\_j^{max}, Y_jmin≤Y_jmaxY\_j^{min} \le Y\_j^{max}.

출력

Для каждого запроса в отдельной строке выведите ответ на этот запрос.

예제2

  1. 예제 1

    입력
    1 1
    30 239
    13 42 11 100500
    
    예상 출력
    1
    
  2. 예제 2

    입력
    4 2
    0 0
    2 0
    0 2
    2 2
    -1 3 -1 3
    1 5 1 5
    
    예상 출력
    4
    1