#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T> inline void read(T &t) {
	t=0;char c=getchar();long long f=1;
	while(!isdigit(c)) {if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)) t=(t<<3)+(t<<1)+(c^'0'),c=getchar();
	t*=f;
}
template <typename T, typename ... Args> inline void read(T &t,Args&... args){read(t);read(args...);}
template <typename T> inline void write(T x,char c='\0'){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
	if(c!='\0') putchar(c);
}
inline long long read()
{
	long long t=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)) t=(t<<3)+(t<<1)+(c^'0'),c=getchar();
	return t*f;
}
int n,t,c,d;
vector<int>a(200005),b(200005);
vector<__gnu_pbds::priority_queue<int> >q(200005);
vector<__gnu_pbds::priority_queue<int>::point_iterator>id(400005);
int main()
{
	read(n,t);
	for(int i=1;i<=n;i++)
	{
		read(a[i],b[i]);
		id[i]=q[b[i]].push(a[i]);
	}
	for(int i=1;i<=100000;i++)
		if(!q[i].empty())
			id[i+n]=q[0].push(-q[i].top());
	while(t--)
	{
		read(c,d);
		q[b[c]].erase(id[c]);
		q[0].erase(id[b[c]+n]);
		if(!q[b[c]].empty())
			id[b[c]+n]=q[0].push(-q[b[c]].top());
		b[c]=d;
		id[c]=q[b[c]].push(a[c]);
		if(q[b[c]].size()>1)
			q[0].erase(id[b[c]+n]);
		id[b[c]+n]=q[0].push(-q[b[c]].top());
		write(-q[0].top(),'\n');
	}
	return 0;
}