eolymp
bolt
Try our new interface for solving problems
Problems

Прямоугольники online

Прямоугольники online

Time limit 3 seconds
Memory limit 64 MiB

Вася нарисовал на плоскости N различных точек с целыми координатами.

Теперь он хочет уметь быстро отвечать, а сколько точек лежит внутри заданного прямоугольника со сторонами, параллельными осям координат.

Input data

В первой строке задается количество точек N (1N50000). Последующие N строк содержат координаты точекx_iy_i. Следующая строка содержит число запросов M (1M50000). Следующие M строк содержат описания запросов, каждый в формате x_1, y_1, x_2, y_2 (0x_1x_210^9, 0y_1y_210^9). Для каждого запроса нужно сделать две вещи:

  • Посчитать число точек в соответствующем прямоугольнике (включая границы).

  • Все посчитанные точки стереть.

Output data

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

Examples

Input example #1
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
3
0 0 1 1
0 0 2 2
0 0 3 3
Output example #1
4
5
0