#include <fstream>
#include <algorithm>
#include <vector>
struct Point2D {
int x, y;
Point2D(int a, int b) : x(a), y(b)
{
}
bool operator<(const Point2D& a) const
{
return x<a.x;
}
};
Point2D makePoint2D(int x, int y)
{
Point2D point(x, y);
return point;
}
class StaticIntervalTree2D {
private:
int tree_size;
std::vector<int> *intervals; //the root is 1
bool *is_leaf;
//merge all of the x leaves, up the tree
void mergeUp(int x)
{
if(is_leaf[x]) return;
mergeUp(2*x);
mergeUp(2*x+1);
auto p = begin(intervals[2*x]);
auto q = begin(intervals[2*x+1]);
while(p < end(intervals[2*x]) && q < end(intervals[2*x+1])) {
if(*p <= *q) {
intervals[x].push_back(*p);
++p;
}
else {
intervals[x].push_back(*q);
++q;
}
}
while(p < end(intervals[2*x])) {
intervals[x].push_back(*p);
++p;
}
while(q < end(intervals[2*x+1])) {
intervals[x].push_back(*q);
++q;
}
}
//return the number of elements between the rectangle (x1, y1, x2, y2)
int query(int x, int low, int high, int x1, int y1, int x2, int y2) const
{
if(low == x1 && high == x2) {
int a = std::lower_bound(std::begin(intervals[x]), std::end(intervals[x]), y1) - std::begin(intervals[x]);
int b = std::upper_bound(std::begin(intervals[x]), std::end(intervals[x]), y2) - std::begin(intervals[x]);
return b-a;
}
int middle = low + (high-low)/2;
if(x2 <= middle) return query(2*x, low, middle, x1, y1, x2, y2);
else if(middle < x1) return query(2*x+1, middle+1, high, x1, y1, x2, y2);
else {
int sum = query(2*x, low, middle, x1, y1, middle, y2);
sum += query(2*x+1, middle+1, high, middle+1, y1, x2, y2);
return sum;
}
}
public:
//points need to be sorted by x coordinate
StaticIntervalTree2D(std::vector<Point2D>& points)
{
tree_size = points.size()*3;
intervals = new std::vector<int>[tree_size];
is_leaf = new bool[tree_size];
for(int i = 0; i < tree_size; ++i) is_leaf[i] = false;
for(int i = 1; i <= points.size(); ++i) {
int x = 1; //start at root
int low = 1, middle, high = points.size();
while(low != high) {
middle = low + (high-low)/2;
if(i <= middle) {
high = middle;
x = x*2;
}
else {
low = middle+1;
x = x*2+1;
}
}
is_leaf[x] = true;
intervals[x].push_back(points[i-1].y);
}
mergeUp(1);
}
int computePointsInRectangle(std::vector<Point2D>& points, int x1, int y1, int x2, int y2) const
{
//normalize the x coordinates
Point2D point1(x1, y1);
Point2D point2(x2, y2);
x1 = std::lower_bound(std::begin(points), std::end(points), point1) - std::begin(points) + 1;
x2 = std::upper_bound(std::begin(points), std::end(points), point2) - std::begin(points);
//call query with normalized x coordinates
if(x1>x2) return 0;
else return query(1, 1, points.size(), x1, y1, x2, y2);
}
};
int main()
{
std::ifstream in("zoo.in");
std::ofstream out("zoo.out");
int n, m;
std::vector<Point2D> points;
in>>n;
int x, y;
for(int i=0; i<n; ++i) {
in>>x>>y;
points.push_back(makePoint2D(x, y));
}
std::sort(std::begin(points), std::end(points));
StaticIntervalTree2D tree(points);
in>>m;
int x1, y1, x2, y2;
for(int i=0; i<m; ++i) {
in>>x1>>y1>>x2>>y2;
out<<tree.computePointsInRectangle(points, x1, y1, x2, y2)<<'\n';
}
return 0;
}