#2973. 「COI 2010」HRASTOVI

内存限制:32 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

译自 COI 2010 T1. KRALJEVI

在平面直角坐标系上有若干棵橡树,橡树均视为点,且均在整点上。

现在,Ljubo 想铺设一条矩形的步道,矩形的四边均平行于 x 轴或 y 轴,四个顶点均为整点。如果一棵橡树在矩形的一边上,那么这棵橡树将被砍掉。在矩形内部和外部的橡树均不用被砍掉。

Ljubo 给出了 P 种铺设方案。对于每种方案,请求出:有多少棵橡树将被砍掉。

输入格式

第一行一个整数 N ,表示橡树的棵数;

接下来 N 行,每行包含两个整数 X_i,Y_i ,表示一棵橡树的坐标;

接下来一行,一个整数 P ,表示步道的条数;

接下来 P 行,每行四个整数 X_1,Y_1,X_2,Y_2 ,表示矩形的左下角坐标为 (X_1,Y_1) ,右上角坐标为 (X_2,Y_2)

输出格式

输出 P 行,每行输出一个整数,表示要被砍掉的橡树数。

样例

样例输入

6
1 2
3 2
2 3
2 5
4 4
6 3
4
2 2 4 4
2 2 6 5
3 3 5 6
5 1 6 6

样例输出

3
4
0
1

样例说明

数据范围与提示

对于 30\% 的数据, 1\le X_1<X_2\le 10^3,1\le Y_1<Y_2\le 10^3

对于 60\% 的数据, 1\le X_1<X_2\le 10^6,1\le Y_1<Y_2\le 10^6

对于全部数据, 1\le N\le 3\times 10^5,1\le X,Y\le 10^9,1\le X_1<X_2\le 10^9,1\le Y_1<Y_2\le 10^9