#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
const int inf=1e9;
int n,m;
int l[N],r[N];
int stk[N],top;
struct segtree{
	int tr[N*4],lz[N*4];
	void Pushup(int x)
	{
		tr[x]=min(tr[x*2],tr[x*2+1]);
	} 
	void Pushdown(int x)
	{
		if(!lz[x]) return;
		tr[x*2]+=lz[x];
		tr[x*2+1]+=lz[x];
		lz[x*2]+=lz[x];
		lz[x*2+1]+=lz[x];
		lz[x]=0;
	}
	void modify(int l,int r,int L,int R,int x,int v)
	{
		if(l>R||r<L) return;
		if(l>=L&&r<=R)
		{
			tr[x]+=v;
			lz[x]+=v;
			return;
		}
		int mid=(l+r)/2;
		Pushdown(x);
		modify(l,mid,L,R,x*2,v);
		modify(mid+1,r,L,R,x*2+1,v);
		Pushup(x);
	}
	int check(int l,int r,int L,int R,int x)
	{
		if(l>R||r<L) return inf;
		if(l==r) return l;
		int mid=(l+r)/2;
		Pushdown(x);
		int v=inf;
		if(tr[x*2]<=0) v=check(l,mid,L,R,x*2);
		else if(tr[x*2+1]<=0) v=check(mid+1,r,L,R,x*2+1); 
		return v;
	}
	int query(int l,int r,int p,int x)
	{
		if(l==r) return tr[x];
		int mid=(l+r)/2;
		Pushdown(x);
		if(p<=mid) return query(l,mid,p,x*2);
		else return query(mid+1,r,p,x*2+1);
	}
}tr1,tr2,tr3;
int ans[N];
struct node{
	int p,id;
};
vector<node> E[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&l[i],&r[i]),
		tr1.modify(1,n,i,i,1,inf),
		tr2.modify(1,n,i,i,1,inf);
	for(int i=1;i<=m;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		E[l].push_back((node){r,i});
	}
	for(int i=n;i>=1;i--)
	{
		tr1.modify(1,n,i,i,1,-inf);
		tr2.modify(1,n,i,i,1,-inf);
		tr1.modify(1,n,i,i,1,l[i]);
		tr2.modify(1,n,i,i,1,r[i]+1);
		while(1)
		{
			int l1=tr1.check(1,n,i,n,1),l2=tr2.check(1,n,i,n,1);
			if(l1==inf&&l2==inf) break;
			if(l1<l2)
			{
				tr1.modify(1,n,l1,l1,1,1e9);
				tr1.modify(1,n,l1+1,n,1,-1);
				tr2.modify(1,n,l1+1,n,1,-1);
				tr3.modify(1,n,l1,n,1,1);
			}
			else
			{
				tr1.modify(1,n,l2,l2,1,1e9);
				tr1.modify(1,n,l2+1,n,1,1);
				tr2.modify(1,n,l2+1,n,1,1);
				tr3.modify(1,n,l1,n,1,-1);
			}
		}
		for(auto u:E[i]) ans[u.id]=tr3.query(1,n,u.p,1);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}