eolymp
bolt
Try our new interface for solving problems
Problems

Сапер

Сапер

Time limit 1 second
Memory limit 64 MiB

После успешно решенных задач, мальчик Матвей решил сыграть в игру "Сапер". Игра состоит из квадратного поля 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