#include <bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
typedef pair<int, int> pr;
#define up(i, l, r) for(int i = (l); i <= (r); i++)
#define down(i, r, l) for(int i = (r); i >= (l); i--)
const int mod = 1000000007;
const int base = 2333;
const double eps = 1e-6;

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
	return x * f;
}

int n, m, k, Q, T, _, ans = 0;
multiset<int>s[200007],mx;
pr a[200007];
int getend(multiset<int>tmd){auto u=tmd.end();u--;return (*u);}
signed main() {
	n=read(),Q=read();
	for(int i=1;i<=n;i++){
		int x=read(),y=read();
		s[y].insert(x);
		a[i]=pr(x,y);
	}
	for(int i=1;i<=200000;i++)if(!s[i].empty())mx.insert(getend(s[i]));
	while(Q--){
		int num=read(),to=read();
		
		int x=a[num].first,from=a[num].second;
		a[num].second=to;
		int tmp=getend(s[from]);
		auto pos=s[from].find(x);s[from].erase(pos);
		if(!s[from].empty()){
			int now=getend(s[from]);
			if(x==tmp&&now!=tmp){
				pos=mx.find(tmp);
				mx.erase(pos);mx.insert(now);
			}
		}
		else {
			pos=mx.find(x);
			mx.erase(pos);
		}
		
		if(!s[to].empty()){
			tmp=getend(s[to]);
			s[to].insert(x);
			if(x>tmp){
				pos=mx.find(tmp);
				mx.erase(pos);mx.insert(x);
			}
		}
		else{
			s[to].insert(x);
			mx.insert(x);
		}
		
		printf("%d\n",*mx.begin());
	}
	return 0;
}

超了两个点。