#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
	int x,y,v;
	bool operator < (const node &b) const
	{
		return v<b.v;
	}
};
bool cmp(node a,node b)
{
	return a.v<b.v;
}
node f[100001],g[100001],p[100001];
signed main()
{
	int n,m,a,b;
	scanf("%lld%lld%lld%lld",&n,&m,&a,&b);
	for(int i=0;i<a;i++) 
	{
		scanf("%lld%lld",&f[i].x,&f[i].y);
		p[i].x=g[i].x=f[i].x,p[i].y=g[i].y=f[i].y;
		f[i].v=f[i].x+f[i].y;
		g[i].v=g[i].x-g[i].y;
		p[i].v=p[i].x*p[i].y;
	}
	sort(f,f+a,cmp);
	sort(g,g+a,cmp);
	sort(p,p+a,cmp);
	for(int i=0;i<b;i++)
	{
		int xx,yy,t1,t2,t3,s=1e18;
		scanf("%lld%lld",&xx,&yy);
		t1=xx+yy,t2=xx-yy,t3=xx*yy;
		int a1=lower_bound(f,f+a,(node){xx,yy,t1})-f;
		for(int j=a1;j<min(a1+300,a);j++) 
		{
			s=min(s,abs(f[j].x-xx)+abs(f[j].y-yy));
			if(f[j].x>=xx&&f[j].y>=yy) break;
		}
		for(int j=a1;j>=max(a1-300,0LL);j--)
		{
			s=min(s,abs(f[j].x-xx)+abs(f[j].y-yy));
			if(f[j].x<=xx&&f[j].y<=yy) break;
		}
		if(s==0)
		{
			printf("0\n");
			continue;
		}
		int a2=lower_bound(g,g+a,(node){xx,yy,t2})-g;
		for(int j=a2;j<min(a2+300,a);j++)
		{
			s=min(s,abs(g[j].x-xx)+abs(g[j].y-yy));
			if(g[j].x>=xx&&g[j].y<=yy) break;
		}
		for(int j=a2;j>=max(a2-300,0LL);j--)
		{
			s=min(s,abs(g[j].x-xx)+abs(g[j].y-yy));
			if(g[j].x<=xx&&g[j].y>=yy) break;
		}
		int a3=lower_bound(p,p+a,(node){xx,yy,t3})-p;
		for(int j=max(a3-300,0LL);j<min(a3+300,a);j++)
		{
			s=min(s,abs(p[j].x-xx)+abs(p[j].y-yy));
		}
		printf("%lld\n",s);
	}
	return 0;
}

大致思路是找x+y，x-y，x*y都比较接近的300个点（其实甚至下限最低可以不到100个），认为答案一定在这里面，但感觉正确性不太好证明