#include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+10,N=460;
int n,q,K,B,l[MAX],r[MAX],x,y,mn,w[N][MAX],L,R;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
inline int work(int x,int L,int R){
    mn=1e9;
    for(int i=L;i<=R;++i){
        if(x<l[i]){
            mn=min(l[i]-1-x,mn);continue;
        }if(x<=r[i])  mn=min(r[i]-x,mn),++x;
    }return x;
}
signed main(){
    n=read();q=read();K=450;B=(n+K-1)/K;
    for(int i=1;i<=n;++i)  l[i]=read(),r[i]=read();
    // cout<<work(0,2,3)<<endl;
    for(int i=1;i<=B;++i){
        L=(i-1)*K+1,R=min(i*K,n);
        x=0;
        while(x<L){
            y=work(x,L,R);
            // cout<<L<<" "<<R<<" "<<x<<" "<<y<<" "<<mn<<endl;
            mn=min(mn,L-x);
            for(int j=0;j<=mn;++j)  w[i][x+j]=y+j;
            x+=mn+1;
        }
    }
    // cout<<w[3][1]<<endl;
    while(q--){
        x=0;L=read();R=read();
        int a=(L+K-1)/K,b=(R+K-1)/K;
        x=work(x,L,min(a*K,R));
        if(a==b){
            printf("%d\n",x);continue;
        }for(int i=a+1;i<b;++i)  x=w[i][x];
        x=work(x,(b-1)*K+1,R);
        printf("%d\n",x);
    }
}