#include <bits/stdc++.h>
using namespace std;
int x,p,arr[200002];
priority_queue<int,vector<int>,greater<int> >q;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>x>>p;
	q.push(x);
	for(int i=1;i<=p;i++){
		int a,b;
		cin>>a>>b;
		q.push(a);
		q.push(b);
		int l=q.size()/2;
		int op=1;
		while(!q.empty() && q.size()!=l+1){
			arr[op]=q.top();
			q.pop();
			op++;
		}
		cout<<q.top()<<"\n";
		for(int i=1;i<=op-1;i++){
			q.push(arr[i]);
		}
	}
	return 0;
}
/*
奇数个：中位数是第 (n+1)/2 个数据，例如 5 个数据取第 3 个 。
o(n(n/2)
偶数个：中位数是第 n/2 个和第 (n/2+1) 个数据的平均数，例如 4 个数据取第 2、3 个的平均值 。
*/

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCB4LHAsYXJyWzIwMDAwMl07CnByaW9yaXR5X3F1ZXVlPGludCx2ZWN0b3I8aW50PixncmVhdGVyPGludD4gPnE7CmludCBtYWluKCl7Cglpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgljaW4udGllKDApLGNvdXQudGllKDApOwoJY2luPj54Pj5wOwoJcS5wdXNoKHgpOwoJZm9yKGludCBpPTE7aTw9cDtpKyspewoJCWludCBhLGI7CgkJY2luPj5hPj5iOwoJCXEucHVzaChhKTsKCQlxLnB1c2goYik7CgkJaW50IGw9cS5zaXplKCkvMjsKCQlpbnQgb3A9MTsKCQl3aGlsZSghcS5lbXB0eSgpICYmIHEuc2l6ZSgpIT1sKzEpewoJCQlhcnJbb3BdPXEudG9wKCk7CgkJCXEucG9wKCk7CgkJCW9wKys7CgkJfQoJCWNvdXQ8PHEudG9wKCk8PCJcbiI7CgkJZm9yKGludCBpPTE7aTw9b3AtMTtpKyspewoJCQlxLnB1c2goYXJyW2ldKTsKCQl9Cgl9CglyZXR1cm4gMDsKfQovKgrlpYfmlbDkuKrvvJrkuK3kvY3mlbDmmK/nrKwgKG4rMSkvMiDkuKrmlbDmja7vvIzkvovlpoIgNSDkuKrmlbDmja7lj5bnrKwgMyDkuKog44CCCm8obihuLzIpCuWBtuaVsOS4qu+8muS4reS9jeaVsOaYr+esrCBuLzIg5Liq5ZKM56ysIChuLzIrMSkg5Liq5pWw5o2u55qE5bmz5Z2H5pWw77yM5L6L5aaCIDQg5Liq5pWw5o2u5Y+W56ysIDLjgIEzIOS4queahOW5s+Wdh+WAvCDjgIIKKi8=

Mjc4MTE3MDMxCjcKMTY3NjQyOTA5IDUxNzg5NzcyMQoxNDg0MzQzMjMgNTY3NzM5NTk3CjMxOTkyNjk5OSA0ODE2NDI1MzAKNjU5MTk5ODc5IDI1MjUxNjU1Nwo0OTkxMzQwMyA3OTgzMTgwMzQKODk3MDE0MDggODkyNTM3MjAxCjE5OTE2NjY2OCA3NDIyODU4NjkK

278117031
7
167642909 517897721
148434323 567739597
319926999 481642530
659199879 252516557
49913403 798318034
89701408 892537201
199166668 742285869