Logo HelloWorld信息学奥赛题库

少儿编程

时间限制:3 s 空间限制:32 MB

#3710. 「COI 2010」HRASTOVI

统计

题目描述

译自 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$ 行,每行输出一个整数,表示要被砍掉的橡树数。

样例

input

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

output

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$。