#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)
using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
int N,M;
struct punct {
int x,y;
}v[16010];
struct elem {
int* vect;
}arb[524288];
bool cmp(punct,punct);
void formeaza_arb(int,int,int);
int query(int,int,int,int,int,int,int);
int binary_s(int*,int,int);
int main()
{
f>>N;
FOR (i,1,N) {
f>>v[i].x>>v[i].y;
}
sort(v+1,v+N+1,cmp);
/*FOR (i,1,N) {
g<<v[i].x<<' '<<v[i].y<<'\n';
}
g<<'\n';*/
formeaza_arb(1,1,N);
/*int x=3;
FOR (i,1,5) {
g<<arb[x].vect[i]<<'\n';
}
g<<"\n\n";*/
f>>M;
FOR (i,1,M) {
int x1,y1,x2,y2;
f>>x1>>y1>>x2>>y2;
g<<query(1,1,N,x1,y1,x2,y2)<<'\n';
}
f.close();g.close();
return 0;
}
bool cmp(punct a,punct b) {
return a.x<b.x;
}
void formeaza_arb(int nod,int st,int dr) {
//cout<<nod<<' '<<st<<' '<<dr<<'\n';
arb[nod].vect=new int[dr-st+2];
if (st==dr) {
arb[nod].vect[1]=v[st].y;
//cout<<nod<<' '<<st<<' '<<dr<<' '<<v[st].x<<' '<<v[st].y<<'\n';
}
else {
int mij=(st+dr)>>1;
formeaza_arb((nod<<1),st,mij);
formeaza_arb((nod<<1)+1,mij+1,dr);
int limst,limdr;
limst=mij-st+1;
limdr=dr-(mij+1)+1;
int i=1,j=1,dimvect=0;
while (i<=limst && j<=limdr) {
if (arb[(nod<<1)].vect[i]<arb[(nod<<1)+1].vect[j]) {
arb[nod].vect[++dimvect]=arb[(nod<<1)].vect[i];
++i;
}
else {
arb[nod].vect[++dimvect]=arb[(nod<<1)+1].vect[j];
++j;
}
}
while (i<=limst) {
arb[nod].vect[++dimvect]=arb[(nod<<1)].vect[i];
++i;
}
while (j<=limdr) {
arb[nod].vect[++dimvect]=arb[(nod<<1)+1].vect[j];
++j;
}
/*cout<<nod<<'\n';
FOR(i,1,dimvect) {
cout<<arb[nod].vect[i].x<<' '<<arb[nod].vect[i].y<<'\n';
}
cout<<'\n';*/
}
}
int query(int nod,int st,int dr,int x1,int y1,int x2,int y2) {
//cout<<nod<<' '<<st<<' '<<dr<<'\n';
if (x1<=v[st].x && v[dr].x<=x2) {
int pozst,pozdr;
pozst=binary_s(arb[nod].vect,dr-st+1,y1);
pozdr=binary_s(arb[nod].vect,dr-st+1,y2);
while (arb[nod].vect[pozst]<y1) {
++pozst;
}
while (arb[nod].vect[pozst-1]==arb[nod].vect[pozst]) {
--pozst;
}
while (arb[nod].vect[pozdr]>y2) {
--pozdr;
}
while (arb[nod].vect[pozdr+1]==arb[nod].vect[pozdr]) {
++pozdr;
}
//cout<<pozdr<<' '<<pozst<<'\n';
return pozdr-pozst+1;
}
else if (st==dr) {
return 0;
}
else {
int mij=(st+dr)>>1;
int rez=0;
if (x1<=v[mij].x) {
rez+=query((nod<<1),st,mij,x1,y1,x2,y2);
}
if (v[mij].x<x2) {
rez+=query((nod<<1)+1,mij+1,dr,x1,y1,x2,y2);
}
return rez;
}
}
int binary_s(int* vect,int dim,int val) {
int st=1,dr=dim;
while (st<dr) {
int mij=(st+dr)>>1;
if (val<vect[mij]) {
dr=mij-1;
}
else if (val>vect[mij]) {
st=mij+1;
}
else {
return mij;
}
}
return st;
}
/*#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)
using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
int N,M;
struct punct {
int x,y;
}v[16010];
struct item {
punct elem;
item* next=NULL;
};
struct lista {
item *left,*right;
};
lista arb[16390];
struct idekam{
int* vect;
}ca[16390];
bool cmp(punct,punct);
void formeaza_arb(int,int,int);
int query(int,int,int,int,int,int,int);
int main()
{
f>>N;
FOR (i,1,N) {
f>>v[i].x>>v[i].y;
}
sort(v+1,v+N+1,cmp);
FOR (i,1,N) {
g<<v[i].x<<' '<<v[i].y<<'\n';
}
g<<'\n';
formeaza_arb(1,1,N);
item* p=arb[1].left;
while (p->next!=NULL) {
g<<p->elem.x<<' '<<p->elem.y<<'\n';
p=p->next;
}
FOR (i,1,M) {
int x1,y1,x2,y2;
f>>x1>>y1>>x2>>y2;
g<<query(1,1,N,x1,y1,x2,y2)<<'\n';
}
f.close();g.close();
return 0;
}
bool cmp(punct a,punct b) {
return a.x<b.x;
}
void formeaza_arb(int nod,int st,int dr) {
ca[nod].vect=new int[dr-st+1];
cout<<ca[nod].vect[dr-st];
arb[nod].left=arb[nod].right=new item;
//cout<<st<<' '<<dr<<'\n';
if (st==dr) {
item* p=new item;
arb[nod].right->elem.x=v[st].x;
arb[nod].right->elem.y=v[st].y;
arb[nod].right->next=p;
arb[nod].right=p;
}
else {
int mij=(st+dr)>>1;
formeaza_arb((nod<<1),st,mij);
formeaza_arb((nod<<1)+1,mij+1,dr);
item* stanga=arb[(nod<<1)].left;
item* dreapta=arb[(nod<<1)+1].left;
while (stanga->next!=NULL && dreapta->next!=NULL) {
if ((stanga->elem.y)<(dreapta->elem.y)) {
item* p=new item;
arb[nod].right->elem=stanga->elem;
arb[nod].right->next=p;
arb[nod].right=p;
stanga=stanga->next;
cout<<'s';
}
else {
item* p=new item;
arb[nod].right->elem=dreapta->elem;
arb[nod].right->next=p;
arb[nod].right=p;
dreapta=dreapta->next;
cout<<'d';
}
}
while (stanga->next!=NULL) {
item* p=new item;
arb[nod].right->elem=stanga->elem;
arb[nod].right->next=p;
arb[nod].right=p;
stanga=stanga->next;
cout<<'s';
}
while (dreapta->next!=NULL) {
item* p=new item;
arb[nod].right->elem=dreapta->elem;
arb[nod].right->next=p;
arb[nod].right=p;
dreapta=dreapta->next;
cout<<'d';
}
}
cout<<'\n'<<nod<<' '<<st<<' '<<dr;
cout<<"\n\n";
}
int query(int nod,int st,int dr,int x1,int y1,int x2,int y2) {
if (x1<=v[st].x && v[dr].x<=x2) {
}
else {
int mij=(st+dr)>>1,rez=0;
if (x1<=mij) {
rez+=query((nod<<1),st,mij,x1,y1,x2,y2);
}
if (mij<x2) {
rez+=query((nod<<1)+1,mij+1,dr,x1,y1,x2,y2);
}
}
}
*/
/*#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)
#define inf 2000000100
using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
int N,dimv,M,nrpat,dimlast;
int arb[16390];
int rez[100010];
int last[100010];
vector<int> puncte_pat[100010];
bitset<100010> verif;
struct pct {
int x,y;
}punct[16010];
struct elem {
bool e_punct=true;
int x=0,y=0,poz=0,pozorig=0;
}v[116010];
struct pat {
int x1,y1,x2,y2,pozorig=0;
}patrat[100010];
bool compar_patrat(pat,pat);
bool compar_punct(pct,pct);
bool cmp(elem,elem);
int binsearch(int);
void update(int,int,int,int,int,int);
int query(int,int,int,int,int);
int main()
{
f>>N;
FOR (i,1,N) {
int x,y;
f>>x>>y;
punct[i].x=x;
punct[i].y=y;
}
sort (punct+1,punct+N+1,compar_punct);
FOR (i,1,N) {
//g<<punct[i].x<<' '<<punct[i].y<<'\n';
v[++dimv].x=punct[i].x;
v[dimv].y=punct[i].y;
v[dimv].poz=i;
}
f>>M;
FOR (i,1,M) {
int x1,x2,y1,y2;
f>>x1>>y1>>x2>>y2;
patrat[i].x1=x1;
patrat[i].y1=y1;
patrat[i].x2=x2;
patrat[i].y2=y2;
patrat[i].pozorig=i;
}
patrat[M+1].x1=patrat[M+1].y1=inf;
sort (patrat+1,patrat+M+2,compar_patrat);
FOR (i,1,M) {
g<<patrat[i].x1<<' '<<patrat[i].y1<<' '<<patrat[i].x2<<' '<<patrat[i].y2<<' '<<'\n';
}
FOR (i,1,M) {
v[++dimv].e_punct=false;
v[dimv].x=patrat[i].x1;
v[dimv].y=patrat[i].y1;
v[dimv].poz=i;
v[dimv].pozorig=patrat[i].pozorig;
v[++dimv].e_punct=false;
v[dimv].x=patrat[i].x2;
v[dimv].y=patrat[i].y2;
v[dimv].poz=i;
v[dimv].pozorig=patrat[i].pozorig;
}
sort(v+1,v+dimv+1,cmp);
FOR (i,1,dimv) {
cout<<v[i].e_punct<<' '<<v[i].x<<' '<<v[i].y<<'\n';
if (v[i].e_punct && nrpat) {
int poz=v[i].poz;
puncte_pat[last[dimlast]].pb(poz);
update(1,1,N,poz,poz,1);
}
else if (!v[i].e_punct) {
if (!verif.test(v[i].poz)) {
verif.set(v[i].poz,1);
++nrpat;
last[++dimlast]=v[i].poz;
}
else {
verif.set(v[i].poz,0);
--nrpat;
int left,right;
left=binsearch(patrat[v[i].poz].y1);
while (punct[left].y<patrat[v[i].poz].y1) {
++left;
}
while (punct[left-1].y==patrat[v[i].poz].y1) {
--left;
}
right=binsearch(patrat[v[i].poz].y2);
while (punct[right].y>patrat[v[i].poz].y2) {
--right;
}
while (punct[right+1].y==patrat[v[i].poz].y2) {
++right;
}
rez[v[i].pozorig]=query(1,1,N,left,right);
if (!nrpat) {
update(1,1,N,1,N,0);
}
else if (v[i].poz==last[1]) {
for (unsigned int k=0;k<puncte_pat[last[1]].size();++k) {
update(1,1,N,puncte_pat[last[1]][k],puncte_pat[last[1]][k],0);
}
}
if (v[i].poz==last[dimlast]) {
--dimlast;
}
}
}
}
FOR (i,1,M) {
g<<rez[i]<<'\n';
}
f.close();g.close();
return 0;
}
int binsearch(int val) {
int left=1,right=N;
while (left<right) {
int mij=(left+right)>>1;
if (punct[mij].y==val) {
return mij;
}
else if (val<punct[mij].y) {
right=mij-1;
}
else {
left=mij+1;
}
}
return left;
}
void update(int nod,int st,int dr,int a,int b,int val) {
if (a<=st && dr<=b) {
if (val==1) {
arb[nod]=dr-st+1;
}
else {
arb[nod]=0;
}
}
else {
int mij=(st+dr)>>1;
if (arb[nod]==0) {
arb[(nod<<1)]=arb[(nod<<1)+1]=0;
}
else if (arb[nod]==dr-st+1) {
arb[(nod<<1)]=mij-st+1;
arb[(nod<<1)+1]=dr-(mij+1)+1;
}
if (a<=mij) {
update((nod<<1),st,mij,a,b,val);
}
if (mij<b) {
update((nod<<1)+1,mij+1,dr,a,b,val);
}
arb[nod]=arb[(nod<<1)]+arb[(nod<<1)+1];
}
}
int query(int nod,int st,int dr,int a,int b) {
if (a<=st && dr<=b) {
return arb[nod];
}
else {
int mij=(st+dr)>>1;
if (arb[nod]==0) {
arb[(nod<<1)]=arb[(nod<<1)+1]=0;
}
else if (arb[nod]==dr-st+1) {
arb[(nod<<1)]=mij-st+1;
arb[(nod<<1)+1]=dr-(mij+1)+1;
}
int rez=0;
if (a<=mij) {
rez+=query((nod<<1),st,mij,a,b);
}
if (mij<b) {
rez+=query((nod<<1)+1,mij+1,dr,a,b);
}
arb[nod]=arb[(nod<<1)]+arb[(nod<<1)+1];
return rez;
}
}
bool compar_patrat(pat a,pat b) {
if (a.x1!=b.x1) {
return a.x1<b.x1;
}
else {
return a.y1<b.y1;
}
}
bool compar_punct(pct a,pct b) {
return a.y<b.y;
}
bool cmp(elem a,elem b) {
if (a.x!=b.x) {
return a.x<b.x;
}
else {
if (!a.e_punct) {
return true;
}
else {
return false;
}
}
}
*/