using namespace std;↵
inline int read()↵
{↵
int s=0,f=1;↵
char c=getchar();↵
while(c<'0'||c>'9')↵
{↵
if(c=='-')↵
f=-1;↵
c=getchar(); ↵
}↵
while(c>='0'&&c<='9')↵
{↵
s=s*10+c-'0';↵
c=getchar();↵
}↵
return s*f;↵
}↵
↵
int lg[1000007];↵
inline void Init()↵
{↵
for(int i=1;i<=1000000;++i)↵
lg[i]=log2(i);↵
}↵
↵
int n,m,q;↵
struct Point{↵
int x,y;↵
}p[300007];↵
inline bool cmp0(Point x,Point y)↵
{↵
if(x.x==y.x)↵
return x.y<y.y;↵
return x.x<y.x; ↵
}↵
struct Node{↵
int x,l,r,id;↵
};↵
struct Tree{↵
vector <int> a[1000007];↵
Node d[1000007];↵
vector <int> c[1000007];↵
int cnt;↵
int depth[1000007],fa[1000007][21];↵
inline void dfs0(int x,int Fa)↵
{↵
depth[x]=depth[Fa]+1;↵
fa[x][0]=Fa;↵
for(int i=1;i<=lg[depth[x]];++i)↵
fa[x][i]=fa[fa[x][i-1]][i-1];↵
for(int i=0;i<a[x].size();++i)↵
{↵
int v=a[x][i];↵
if(v==Fa)↵
continue;↵
dfs0(v,x);↵
}↵
}↵
inline int LCA(int x,int y)↵
{↵
if(depth[x]<depth[y])↵
swap(x,y);↵
while(depth[x]>depth[y])↵
x=fa[x][lg[depth[x]-depth[y]]];↵
if(x==y)↵
return x;↵
for(int i=lg[depth[x]];i>=0;--i)↵
{↵
if(fa[x][i]!=fa[y][i])↵
x=fa[x][i],y=fa[y][i];↵
}↵
return fa[x][0];↵
}↵
inline int query_id(int x,int y)↵
{↵
int lca=LCA(x,y);↵
if(lca==0)↵
return -1;↵
return depth[x]+depth[y]-2*depth[lca];↵
}↵
inline void build(int id)↵
{↵
if(id==0||id==2)↵
{↵
if(id==2)↵
{↵
for(int i=1;i<=m;++i)↵
{↵
int x=p[i].x,y=p[i].y;↵
p[i].x=x+y;↵
p[i].y=x-y;↵
}↵
}↵
sort(p+1,p+m+1,cmp0);↵
int l1=1;↵
for(int i=1+(id==2);i<=n*(1+(id==2));++i)↵
{↵
++cnt;↵
d[cnt].x=i,d[cnt].id=cnt;↵
if(id==0)↵
d[cnt].l=1;↵
else↵
d[cnt].l=-min(i-2,2*n-i);↵
while(l1<=m&&p[l1].x==i)↵
{↵
if(p[l1].y==d[cnt].l)↵
d[cnt].l=p[l1].y+1;↵
else↵
{↵
d[cnt].r=p[l1].y-1,c[i].push_back(cnt);↵
++cnt;↵
d[cnt].x=i,d[cnt].l=p[l1].y+1,d[cnt].id=cnt;↵
}↵
++l1;↵
}↵
if(id==0)↵
{↵
if(d[cnt].l>n)↵
--cnt;↵
else↵
d[cnt].r=n,c[i].push_back(cnt);↵
}↵
else↵
{↵
if(d[cnt].l>min(i-2,2*n-i))↵
--cnt;↵
else↵
d[cnt].r=min(i-2,2*n-i),c[i].push_back(cnt);↵
}↵
}↵
for(int x=1+(id==2);x<n*(1+(id==2));++x)↵
{↵
int l1=0;↵
for(int i=0;i<c[x].size();++i)↵
{↵
while(l1<c[x+1].size()&&d[c[x+1][l1]].r<d[c[x][i]].l-(id==0))↵
++l1;↵
bool flag=0;↵
while(l1<c[x+1].size()&&d[c[x+1][l1]].l<=d[c[x][i]].r+(id==0))↵
{↵
a[c[x][i]].push_back(c[x+1][l1]);↵
a[c[x+1][l1]].push_back(c[x][i]);↵
++l1;↵
flag=1;↵
}↵
if(flag)↵
--l1;↵
}↵
}↵
for(int i=1;i<=cnt;++i)↵
{↵
if(!depth[i])↵
dfs0(i,0);↵
}↵
if(id==2)↵
{↵
for(int i=1;i<=m;++i)↵
{↵
int x=p[i].x,y=p[i].y;↵
p[i].x=(x+y)/2;↵
p[i].y=(x-y)/2;↵
}↵
}↵
}↵
else if(id==1)↵
{↵
for(int i=1;i<=m;++i)↵
swap(p[i].x,p[i].y);↵
build(0);↵
for(int i=1;i<=m;++i)↵
swap(p[i].x,p[i].y);↵
}↵
else if(id==3)↵
{↵
for(int i=1;i<=m;++i)↵
p[i].y=n+1-p[i].y;↵
build(2);↵
for(int i=1;i<=m;++i)↵
p[i].y=n+1-p[i].y;↵
}↵
↵
}↵
inline int Query(int id,int sx,int sy,int tx,int ty)↵
{↵
int x=0,y=0;↵
if(id==0)↵
{↵
for(int i=0;i<c[sx].size();++i)↵
{↵
if(d[c[sx][i]].l<=sy&&sy<=d[c[sx][i]].r)↵
{↵
x=c[sx][i];↵
break;↵
}↵
}↵
for(int i=0;i<c[tx].size();++i)↵
{↵
if(d[c[tx][i]].l<=ty&&ty<=d[c[tx][i]].r)↵
{↵
y=c[tx][i];↵
break;↵
}↵
}↵
assert(x&&y);↵
return query_id(x,y);↵
}↵
else if(id==1)↵
{↵
return Query(0,sy,sx,ty,tx);↵
}↵
else if(id==2)↵
{↵
return Query(0,sx+sy,sx-sy,tx+ty,tx-ty);↵
}↵
else↵
{↵
return Query(2,sx,n+1-sy,tx,n+1-ty);↵
}↵
}↵
}tree[4];↵
int main()↵
{↵
Init();↵
n=read(),m=read(),q=read();↵
for(int i=1;i<=m;++i)↵
p[i].x=read(),p[i].y=read();↵
for(int i=0;i<4;++i)↵
tree[i].build(i);↵
int sx,sy,tx,ty;↵
while(q--)↵
{↵
sx=read(),sy=read(),tx=read(),ty=read();↵
int ans=0;↵
for(int i=0;i<4;++i)↵
{↵
ans+=tree[i].Query(i,sx,sy,tx,ty)*(1+(i<2));↵
if(ans==-2)↵
{↵
assert(i==0);↵
break;↵
}↵
}↵
ans/=2;↵
printf("%d\n",ans);↵
}↵
return 0;↵
}
