#include <bits/stdc++.h>
#define MAX_N 16000
#define MAX_Q 100000
using namespace std;
typedef long long lint;
const lint MAX = (lint)(1e9) * 2;
const int DEBUG = 0;
int n;
struct coord
{
int x, y;
};
coord v[MAX_N + 1];
int x[MAX_N + 1];
int y[MAX_N + 1];
int kx, ky;
int dx[MAX_N + 1];
int dy[MAX_N + 1];
vector <int> g[(MAX_N << 2) + 1];
ifstream f("zoo.in");
int getNr()
{
lint nr = 1LL * rand() * rand() % MAX;
if(rand() & 1)
nr *= (-1);
return nr;
}
void readFile()
{
srand(time(0));
if(DEBUG)
{
n = 16000;
for(int i = 1; i <= n; i ++)
{
//lint nr = 1LL * rand() * rand() % MAX;
v[i].x = getNr();
// nr = 1LL * rand() * rand() % MAX;
v[i].y = getNr();
x[i] = v[i].x;
y[i] = v[i].y;
}
cout << "GATA GEN NR\n";
return;
}
f >> n;
for(int i = 1; i <= n; i ++)
{
f >> v[i].x >> v[i].y;
x[i] = v[i].x;
y[i] = v[i].y;
}
}
void getDiff(int a[], int d[], int &k)
{
k = 1;
d[1] = a[1];
for(int i = 2; i <= n; i ++)
{
// cout << a[i] << " ";
if(a[i] != a[i - 1])
d[++ k] = a[i];
}
// cout << "\n";
// cout << k << "\n";
}
int cautBin(int a[], int n, int nr)
{
int i = 0;
int pas = 1 << 13;
while(pas != 0)
{
if(i + pas <= n && a[i + pas] <= nr)
i += pas;
pas >>= 1;
}
return i;
}
int cautBin2(int a[], int n, int nr)
{
int i = 0;
int pas = 1 << 13;
while(pas != 0)
{
if(i + pas <= n && a[i + pas] < nr)
i += pas;
pas >>= 1;
}
return i + 1;
}
void baga(int poz, int st, int dr, int a, int y)
{
if(st == dr)
{
// assert(poz <= 2*n);
// cout << poz << "\n";
g[poz].push_back(y);
return;
}
int mid = (st + dr) >> 1;
if(a <= mid)
baga(poz << 1, st, mid, a, y);
else
baga((poz << 1) + 1, mid + 1, dr, a, y);
}
void comb(int a, int b, int c)
{
int i = 0, j = 0;
while(i < g[b].size() && j < g[c].size())
{
if(g[b][i] < g[c][j])
{
g[a].push_back(g[b][i]);
i ++;
}
else
{
g[a].push_back(g[c][j]);
j ++;
}
}
while(i < g[b].size())
{
g[a].push_back(g[b][i]);
i ++;
}
while(j < g[c].size())
{
g[a].push_back(g[c][j]);
j ++;
}
// cout << " DIM " << g[b].size() + g[c].size() << " = " << g[a].size() << "\n";
}
int done[MAX_N * 4 + 1];
void build(int poz, int st, int dr, int a)
{
if(st == dr)
{
done[poz] = 1;
return;
}
int mid = (st + dr) >> 1;
if(a <= mid)
build(poz << 1, st, mid, a);
else
build((poz << 1) + 1, mid + 1, dr, a);
// cout << mid + 1 << " " << dr << "\n";
if(mid + 1 <= dr && done[poz << 1] && done[(poz << 1) + 1] && done[poz] == 0)
comb(poz, poz << 1, (poz << 1) + 1), done[poz] = 1;
else if(mid + 1 > dr && done[poz << 1] && done[poz] == 0)
{
done[poz] = 1;
for(auto u : g[poz << 1])
g[poz].push_back(u);
}
// cout << " SUNTEM " << poz << " " << st << " " << dr << " " << a << " DONE " << done[poz] << "\n";
/* cout << "AVEM \n";
for(auto u : g[poz])
cout << u << " ";
cout << "\n";*/
}
void solve()
{
sort(x + 1, x + n + 1);
sort(y + 1, y + n + 1);
getDiff(x, dx, kx);
getDiff(y, dy, ky);
for(int i = 1; i <= n; i ++)
{
int px = cautBin(dx, kx, v[i].x);
int py = cautBin(dy, ky, v[i].y);
baga(1, 1, kx, px, py);
}
// cout << "DAM NBUILD\n";
for(int i = 1; i <= n; i ++)
build(1, 1, kx, i);
}
int rez;
void getRez(int poz, int st, int dr, int a, int b, int y1, int y2)
{
//if(poz != 0)
//cout << " SUNTEM " << poz << " ST DR " << st << " " << dr << " X1 X2 " << a << " " << b << " Y1 Y2 " << y1 << " " << y2 << "\n";
if(st == a && dr == b)
{
vector <int> :: iterator it = lower_bound(g[poz].begin(), g[poz].end(), y1);
vector <int> :: iterator it2 = upper_bound(g[poz].begin(), g[poz].end(), y2);
it2 --;
/*
for(auto u : g[poz])
cout << u << " " ;
cout << "\n";*/
// cout << "PENTRU " << st << " " << dr << " " << " AVEM " << y1 << " " << y2 << " " << (it2 - it + 1) << "\n";
if(it <= it2)
rez += (it2 - it + 1);
return;
}
int mid = (st + dr) >> 1;
if(b <= mid)
getRez(poz << 1, st, mid, a, b, y1, y2);
if(a > mid)
getRez((poz << 1) + 1, mid + 1, dr, a, b, y1, y2);
if(a <= mid && b > mid)
{
getRez(poz << 1, st, mid, a, mid, y1, y2);
getRez((poz << 1) + 1, mid + 1, dr, mid + 1, b, y1, y2);
}
}
int getBrut(int x1, int y1, int x2, int y2)
{
int rez = 0;
for(int i = 1; i <= n; i ++)
{
if(v[i].x >= x1 && v[i].x <= x2 && v[i].y >= y1 && v[i].y <= y2)
rez ++;
}
return rez;
}
void ansQues()
{
ofstream g("zoo.out");
int q;
if(DEBUG)
q = MAX_Q;
else
f >> q;
while(q > 0)
{
q --;
int x1, y1, x2, y2;
if(DEBUG == 1)
{
x1 = getNr();
y1 = getNr();
x2 = getNr();
y2 = getNr();
if(x1 > x2)
swap(x1, x2);
if(y1 > y2)
swap(y1, y2);
}
else
f >> x1 >> y1 >> x2 >> y2;
// cout << " RUM BRUT " << q << "\n";
//
// int rez2 = getBrut(x1, y1, x2, y2);
// cout << "GATA BRUT " << q << "\n";
if(x1 > dx[kx] || x2 < dx[1] || y1 > dy[ky] || y2 < dy[1])
{
// if(rez2 != 0)
// assert(1 == 0);
g << "0\n";
continue;
}
// cout << x1 << " " << x2 << " " << y1 << " " << y2 << "\n";
x1 = cautBin2(dx, kx, x1);
x2 = cautBin(dx, kx, x2);
y1 = cautBin2(dy, ky, y1);
y2 = cautBin(dy, ky, y2);
if(x1 > x2 || y1 > y2)
{
g << "0\n";
continue;
}
// cout << "GATA CBIN\n";
// cout << x1 << " " << x2 << " " << y1 << " " << y2 << "\n";
// cout << dx[x1] << " " << dx[x2] << " " << dy[y1] << " " << dy[y2] << "\n";
// cout << " Q " << x1 << " " << y1 << " DREAPTA JOS " << x2 << " " << y2 << "\n";
rez = 0;
getRez(1, 1, kx, x1, x2, y1, y2);
// cout << "GATA GETREZ\n";
if(DEBUG == 1)
{
// if(rez != rez2)
// cout << rez << " " << rez2 << "\n";
// assert(rez == rez2);
}
else
g << rez << "\n";
}
}
int main()
{
readFile();
solve();
// cout << "GATA SOLVE\n";
ansQues();
return 0;
}