Problems
Сапер
Сапер
После успешно решенных задач, мальчик Матвей решил сыграть в игру "Сапер". Игра состоит из квадратного поля N * N, некоторые ячейки которого, содержат бомбы. Ваша задача – быстро отвечать на запросы количества бомб на подпрямоугольнике. Поскольку Матвею нужно еще решать задачи, времени на запросы у него нет, поэтому он просит вас помочь ему в этом.
Input data
Число точек N(1 ≤ N ≤ 10^5
). Далее N точек (X; Y) с целочисленными координатами. Все X иY различны (0 ≤ X; Y≤ N-1). Далее число запросов M(1 ≤ M ≤ 10^5
). В следующих M строках заданы запросы вида x1 y1 x2 y2.
Output data
Вы должны вывести M строк в каждой из которых записано одно число - количество бомб на подпрямоугольнике.
Examples
Input example #1
11 8 0 7 9 4 5 1 7 6 1 2 10 10 2 0 3 5 8 9 6 3 4 7 1 5 9 10 3 0 7 9 2 0 6 4 3 1 4 2 0 2 3 8 3 5 5 7 6 0 9 4
Output example #1
6 5 2 0 3 1 2