#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
const int yyj=1e9,inf=2e9;
#define eb emplace_back
int n,Q;
int m,b[N],nw[N];
struct Point{int x,y,z;}a[N];
vector<Point>qq;
namespace SGT
{
	#define PII pair<int,int>
	PII t1[N<<2],t2[N<<2];
	inline PII gmin(PII x,PII y){return x.first<y.first?x:y;}
	void build(int p,int l,int r)
	{
		t1[p]=t2[p]={inf,0};
		if(l==r) return ;
		int mid=(l+r)>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
	}
	inline void push_up(int p)
	{
		t1[p]=gmin(t1[p<<1],t1[p<<1|1]);
		t2[p]=gmin(t2[p<<1],t2[p<<1|1]);
	}
	void update(int p,int l,int r,int x,int y,int z,int pos)
	{
		if(l==r) return t1[p]={-y-z,pos},t2[p]={-y+z,pos},void();
		int mid=(l+r)>>1;
		if(x<=mid) update(p<<1,l,mid,x,y,z,pos);
		else update(p<<1|1,mid+1,r,x,y,z,pos);
		push_up(p);
	}
	void clr(int p,int l,int r,int x)
	{
		t1[p]=t2[p]={inf,0};
		if(l==r) return ;
		int mid=(l+r)>>1;
		if(x<=mid) clr(p<<1,l,mid,x);
		else clr(p<<1|1,mid+1,r,x);
	}
	PII query1(int p,int l,int r,int x,int y)
	{
		if(x<=l&&y>=r) return t1[p];
		int mid=(l+r)>>1;PII ret={inf,0};
		if(x<=mid) ret=gmin(ret,query1(p<<1,l,mid,x,y));
		if(y>mid) ret=gmin(ret,query1(p<<1|1,mid+1,r,x,y));
		return ret;
	}
	PII query2(int p,int l,int r,int x,int y)
	{
		if(x<=l&&y>=r) return t2[p];
		int mid=(l+r)>>1;PII ret={inf,0};
		if(x<=mid) ret=gmin(ret,query2(p<<1,l,mid,x,y));
		if(y>mid) ret=gmin(ret,query2(p<<1|1,mid+1,r,x,y));
		return ret;
	}
}using namespace SGT;
int ans[N];
vector<Point>c;
void solve(int l,int r,vector<Point>q)
{
	if(l>=r) return ;
	int ret=inf,u=0,v=0;
	for(int i=l;i<=r;i++) c.eb(a[i]);
	sort(c.begin(),c.end(),[&](Point x,Point y){return x.x<y.x;});
	for(Point i:c)
	{
		int x=i.x,y=i.y,z=nw[i.z];
		PII L=query1(1,1,m,1,z),R=query2(1,1,m,z,m);
		L.first+=x+y;R.first+=x-y;L=gmin(L,R);
		if(L.first<ret)
		{
			ret=L.first;
			u=L.second;v=i.z;
		}
		update(1,1,m,z,x,y,i.z);
	}
	for(Point i:c)
		clr(1,1,m,nw[i.z]);
	c.clear();
	// printf("l=%d r=%d u=%d v=%d ret=%d\n",l,r,u,v,ret);
	vector<Point>q1,q2;
	if(u>v) swap(u,v);
	for(Point i:q)
	{
		if(i.x<=u&&i.y>=v)
			ans[i.z]=ret;
		else if(i.y<v) 
			q1.eb(i);
		else
			q2.eb(i);
	}
	solve(l,v-1,q1);
	solve(u+1,r,q2);
}
int main()
{
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	scanf("%d%d",&n,&Q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
		b[++m]=a[i].y;a[i].z=i;
	}
	sort(b+1,b+m+1);m=unique(b+1,b+m+1)-b-1;
	for(int i=1;i<=n;i++) nw[i]=lower_bound(b+1,b+m+1,a[i].y)-b;
	for(int i=1;i<=Q;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		qq.eb((Point){x,y,i});
	}
	build(1,1,m);
	solve(1,n,qq);
	for(int i=1;i<=Q;i++)
		printf("%d\n",ans[i]);
}