Wa on 2 and 5

#include<bits/stdc++.h>
#define int long long int
#define R register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline int read(){R int x=0,t=1;R char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
int x[50000001],t[50000001],d[5000001];
int s[50000001],n,m;
struct Node
{
	int x,t,id;
}a[20000011];
inline bool cmp(Node xx,Node yy)
{
	return xx.t<yy.t;
}
priority_queue<int>q;
int find(int v)
{
	int l=1,r=n;
	while(l<r){
		int mid=(l+r)/2;
	//	cout << l << " " << r << '\n';
		//cout << a[mid].t << " " << v << '\n';
		if(a[mid].t<=v) l=mid+1;
		else r=mid;
	}
	//if(v==100){
	//	cout << "%%%";
	//}
	F(i,r,l){
		if(a[i].t>=v) return i;
	}
	return n+1;
}
inline void solve()
{
	//0  1 3 5  7
	n=read(),m=read();
	F(i,1,n){
		a[i].x=read(),a[i].t=read(),a[i].id=i;
		if(i>1){
			int vv=abs(a[i-1].x-a[i].x)/abs(a[i-1].t-a[i].t);
			q.push(vv);
		}
	}
	sort(a+1,a+1+n,cmp);
	for(int i = 1;i<=n;i++) d[a[i].id]=i;
	F(i,1,n){
		if(i>1){
			int vv=abs(a[i-1].x-a[i].x)/abs(a[i-1].t-a[i].t);
			q.push(vv);
		}
	}
	if(n==3){
		assert(0);
	}
	F(i,1,m){
		int u=read(),v=read();
		u=d[u];
		if(v==a[u].t){
			cout << q.top() << '\n';
			continue;
		}
		int v1=abs(a[u-1].x-a[u].x)/abs(a[u-1].t-a[u].t);
		int v2=abs(a[u+1].x-a[u].x)/abs(a[u+1].t-a[u].t);
		int maxn=0,sum=abs(a[u+1].x-a[u-1].x)/abs(a[u+1].t-a[u-1].t);
		if(v1<v2)swap(v1,v2);
		if(q.top()==v1){
			q.pop();
			if(q.top()==v2){
				q.pop();
				sum=q.top();
				q.push(v2);
			}
			else{
				sum=max(sum,q.top());
				q.push(v1);
			}
		}
		else{
			sum=q.top();
		}
		int new_loc=find(v);
		if(new_loc!=n+1){
			if(new_loc==u){
				if(new_loc!=n){
					new_loc++;
					v2=abs(a[new_loc].x-a[u].x)/abs(a[new_loc].t-v);
					new_loc--;
				}
			}
			else
			{
				v2=abs(a[new_loc].x-a[u].x)/abs(a[new_loc].t-v);
			}
		}
		if(new_loc!=1){
			if(new_loc-1==u){
				if(new_loc!=2){
				new_loc--;
				v1=abs(a[new_loc-1].x-a[u].x)/abs(a[new_loc-1].t-v);
				new_loc++;
				}
			}
			else
			{
				v1=abs(a[new_loc-1].x-a[u].x)/abs(a[new_loc-1].t-v);
			}
		}
		sum=max({sum,v1,v2});
		cout << sum << '\n';
	}
}
signed main()
{
	solve();
	return 0;	
}